检索结果-内蒙古大学图书馆

12th International Conference on Learning and Intelligent Optimization (LION)

作者： Gimadi, E. Kh Tsidulko, O. Yu Sobolev Inst Math SB RAS Novosibirsk Russia Novosibirsk State Univ Dept Mech & Math Novosibirsk Russia

ISBN: (纸本)9783030053482;9783030053475

The maximum m-Peripatetic Salesman Problem (m-PSP) consists of determining m edge-disjoint Hamiltonian cycles of maximum total weight in a given complete weighted n-vertex graph. We consider a geometric variant of the problem and describe a polynomial time approximation algorithm for the m-PSP in a normed space of fixed dimension. We prove that the algorithm is asymptotically optimal for m = o(n).

关键词： Maximum traveling salesman problem Maximum m-peripatetic salesman problem Normed space asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

An asymptotically optimal algorithm for the Search for and Evaluation of the Slichter Mode from Long-Term Strain Data

引用

MOSCOW UNIVERSITY PHYSICS BULLETIN 2019年第2期74卷 205-211页

作者： Vinogradov, M. P. Milyukov, V. K. Mironov, A. P. Myasnikov, A. V. Moscow MV Lomonosov State Univ Sternberg State Astron Inst Moscow 119234 Russia

The Slichter mode (S-1(1)) is the longest-period mode of Earth's free oscillations. The period of this mode depends on the difference between the densities of the outer liquid and inner solid cores, thus making its detection very important for the refinement of models of the Earth. Despite numerous attempts at detecting this mode with the use of a network of superconducting gravimeters, there currently is no confirmed experimental data on the observation of the Slichter mode due to its small amplitude on the surface. In this work, it is proposed to detect the Slichter mode using the data from the laser interferometer-strainmeter of the Sternberg State Astronomical Institute of the Moscow State University (Northern Caucasus) with a measuring arm length of 75 m. For this purpose, an asymptotically optimal algorithm was developed for the analysis of data with consideration for their statistical properties, and the processing of synthetic data was modeled to estimate the magnitude of the possible observed effect and the detection indicators.

关键词： Earth's free oscillations Slichter mode deformation modeling asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

asymptotically optimal algorithms for the Prize-Collecting Traveling Salesman Problem on Random Inputs 1

引用

13th International Conference on Learning and Intelligent Optimization (LION)

作者： Gimadi, Edward Kh Tsidulko, Oxana Sobolev Inst Math Novosibirsk Russia Novosibirsk State Univ Dept Mech & Math Novosibirsk Russia

ISBN: (数字)9783030386290

ISBN: (纸本)9783030386290;9783030386283

The Prize-Collecting Traveling Salesman Problem is a class of generalizations of the classic Traveling Salesman Problem (TSP) where it is not necessary to visit all the vertices. Given the edge costs and a certain profit associated with each vertex, the goal is to find a route which satisfies maximum collected profit and minimum traveling costs constraints. We show polynomial-time approximation algorithms for two variants of the problem and establish conditions under which the presented algorithms are asymptotically optimal on random inputs.

关键词： asymptotically optimal algorithm Random inputs NP-hard problem Prize-collecting TSP

来源：评论

学校读者我要写书评

暂无评论

asymptotically optimal dualization algorithms

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2015年第5期55卷 891-905页

作者： Djukova, E. V. Prokofjev, P. A. Russian Acad Sci Dorodnicyn Comp Ctr Moscow 119333 Russia

The design of efficient on average algorithms for discrete enumeration problems is studied. The dualization problem, which is a central enumeration problem, is considered. New asymptotically optimal dualization algorithms are constructed. It is shown that they are superior in time costs to earlier constructed asymptotically optimal dualization algorithms and other available dualization algorithms with different design features.

关键词： dualization Boolean matrix asymptotically optimal algorithm irreducible covering enumeration with a polynomial-time delay

来源：评论

学校读者我要写书评

暂无评论

On asymptotically optimal Approach to the m-Peripatetic Salesman Problem on Random Inputs 9th

On Asymptotically Optimal Approach to the m-Peripatetic Sale...

引用

9th International Conference on Discrete Optimization and Operations Research (DOOR)

作者： Gimadi, Edward Kh. Istomin, Alexey M. Tsidulko, Oxana Yu. Sobolev Inst Math 4 Acad Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova Str Novosibirsk 630090 Russia

ISBN: (纸本)9783319449142;9783319449135

We study the m-Peripatetic Salesman Problem on random inputs. In earlier papers we proposed a polynomial asymptotically optimal algorithm for the m-PSP with different weight functions on random inputs. The probabilistic analysis carried out for that algorithm is not suitable in the case of the m-PSP with identical weight functions. In this paper we present an approach which under certain conditions gives polynomial asymptotically optimal algorithms for the m-PSP on random inputs with identical weight functions and for the m-PSP with different weight functions, as well. We describe in detail the cases of uniform and shifted exponential distributions of random inputs.

关键词： m-PSP asymptotically optimal algorithm Performance guarantees Random inputs Uniform distribution Shifted exponential distribution

来源：评论

学校读者我要写书评

暂无评论

optimal global approximation of systems of jump-diffusion SDEs on equidistant mesh

引用

APPLIED NUMERICAL MATHEMATICS 2022年 179卷 1-26页

作者： Katuza, Andrzej AGH Univ Sci & Technol Fac Appl Math Al Mickiewicza 30 PL-30059 Krakow Poland

In this paper, we provide a construction of two algorithms for approximation of the system of the jump-diffusion SDEs. Both methods are based on the classical Milstein steps and use equidistant discretization points. We construct implementable algorithm and their derivative-free version. We show that constructed methods are asymptotically optimal in the class of methods that use equidistant discretization of the interval [0, T]. Moreover, we report numerical experiments performed for some test equations, which confirm theoretical properties. (c) 2022 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： SDEs with jumps Nonhomogeneous Poisson process Wiener process Minimal error Equidistant mesh asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal global approximation of jump-diffusion SDEs via path-independent step-size control

引用

APPLIED NUMERICAL MATHEMATICS 2018年 128卷 24-42页

作者： Kaluza, Andrzej Przybylowicz, Pawel AGH Univ Sci & Technol Fac Appl Math Mickiewicza 30 PL-30059 Krakow Poland

We provide a construction of an implementable method based on path-independent adaptive step-size control for global approximation of jump-diffusion SDEs. The sampling points are chosen in nonadaptive way with respect to trajectories of the driving Poisson and Wiener processes. However, they are adapted to the diffusion and jump coefficients of the underlying stochastic differential equation and to the values of intensity function of the driving Poisson process. The method is asymptotically optimal in the class of methods that use (possibly) non-equidistant discretization of the interval [0, T] and is more efficient than any method based on the uniform mesh. (C) 2018 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： SDEs with jumps Nonhomogeneous Poisson process Wiener process Minimal error Adaptive step-size control asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Constant Composition Distribution Matching

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第1期62卷 430-434页

作者： Schulte, Patrick Boecherer, Georg Tech Univ Munich Inst Commun Engn D-80333 Munich Germany

Distribution matching transforms independent and Bernoulli(1/2) distributed input bits into a sequence of output symbols with a desired distribution. Fixed-to-fixed length, invertible, and low complexity encoders and decoders based on constant composition and arithmetic coding are presented. The encoder achieves the maximum rate, namely, the entropy of the desired distribution, asymptotically in the blocklength. Furthermore, the normalized divergence of the encoder output and the desired distribution goes to zero in the blocklength.

关键词： Distribution matching fixed length arithmetic coding asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Monotone Dualization Problem and Its Generalizations: Asymptotic Estimates of the Number of Solutions

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2018年第12期58卷 2064-2077页

作者： Djukova, E. V. Zhuravlev, Yu. I. Russian Acad Sci Fed Res Ctr Comp Sci & Control Dorodnicyn Comp Ctr Moscow 119333 Russia

Issues related to the construction of efficient algorithms for intractable discrete problems are studied. Enumeration problems are considered. Their intractability has two aspectsexponential growth of the number of their solutions with increasing problem size and the complexity of finding (enumerating) these solutions. The basic enumeration problem is the dualization of a monotone conjunctive normal form or the equivalent problem of finding irreducible coverings of Boolean matrices. For the latter problem and its generalization for the case of integer matrices, asymptotics for the typical number of solutions are obtained. These estimates are required, in particular, to prove the existence of asymptotically optimal algorithms for monotone dualization and its generalizations.

关键词： intractable discrete problem dualization of monotone conjunctive normal form irreducible covering of Boolean matrix irredundant covering of integer matrix asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive step-size control for global approximation of SDEs driven by countably dimensional Wiener process

引用

NUMERICAL algorithmS 2024年第4期96卷 1699-1725页

作者： Stepien, Lukasz AGH Univ Sci & Technol Fac Appl Math Al A Mickiewicza 30 PL-30059 Krakow Poland

In this paper, we deal with the global approximation of solutions of stochastic differential equations (SDEs) driven by countably dimensional Wiener process. Under certain regularity conditions imposed on the coefficients, we show lower bounds for exact asymptotic error behaviour. For that reason, we analyse separately two classes of admissible algorithms: based on equidistant, and possibly not equidistant meshes. Our results indicate that in both cases, decrease of any method error requires significant increase of the cost term, which is illustrated by the product of cost and error diverging to infinity. This is, however, not visible in the finite-dimensional case. In addition, we propose an implementable, path-independent Euler algorithm with adaptive step-size control, which is asymptotically optimal among algorithms using specified truncation levels of the underlying Wiener process. Our theoretical findings are supported by numerical simulation in Python language.

关键词： Stochastic differential equations Countably dimensional Wiener process Adaptive step-size control Minimal error bounds Information-based complexity asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：