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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Detection and Evaluation of the Slichter Mode Based on Long-Term Strain Observations

引用

IZVESTIYA ATMOSPHERIC AND OCEANIC PHYSICS 2020年第11期56卷 1447-1455页

作者： Milyukov, V. K. Vinogradov, M. P. Mironov, A. P. Myasnikov, A., V Moscow MV Lomonosov State Univ Sternberg Astron Inst Moscow 119992 Russia Russian Acad Sci Vladikavkaz Sci Ctr Vladikavkaz 362027 Republic Of Nor Russia

To search for the Slichter mode (S-1(1)), the longest mode of Earth's free oscillations, long-term (more than 15 years) strain data of the Baksan laser interferometer-strainmeter (with a measuring-arm length of 75 m) of Sternberg Astronomical Institute, Moscow State University (SAI MSU) (Elbrus region, North Caucasus) are used. The detection and estimation of the Slichter mode is performed according to our developed asymptotically optimal algorithm for data analysis with allowance for the properties of seismic noise and mode features, including the parameters of its splitting. The hypothesis of the constant mode excitation is tested. The most probable periods of the Slichter mode and the values of the splitting parameter are determined, and the statistical reliability of the detection is estimated.

关键词： Earth’ s core Earth’ s free oscillations Slichter mode laser interferometer– strainmeter asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

The Slichter Mode Detection and Estimation from Laser Interferometer-Strainmeter Observations of the Chilean Earthquake of February 27, 2010

引用

IZVESTIYA-PHYSICS OF THE SOLID EARTH 2020年第6期56卷 737-748页

作者： Milyukov, V. K. Vinogradov, M. P. Mironov, A. P. Myasnikov, A. V. Moscow MV Lomonosov State Univ Sternberg Astron Inst Moscow 119992 Russia Russian Acad Sci Vladikavkaz Sci Ctr Vladikavkaz 362027 Russia

The Slichter mode (S-1(1)) is the longest-period mode of the free oscillations of the Earth. The period of the Slichter mode directly depends on density jump between the outer liquid and the inner solid core which makes the detection of this oscillation very important for gaining a more detailed insight into the structure of the Earth's interior. Reliable empirical data on the detection of Slichter mode are absent, which is associated with the rather low amplitude of this mode on the surface. In this work, for the first time, an attempt is made to detect the Slichter mode using the strain data from the largest 2010 Chilean earthquake recorded by the Baksan laser interferometer-strainmeter (Sternberg Astronomical Institute of the Moscow State University (SAI MSU)) with a measuring arm length of 75 m in the Elbrus region, North Caucasus. An asymptotically optimal data analysis algorithm that allows for the properties of seismic noise and peculiarities of the mode is developed. Simultaneously with mode detection, the algorithm provides evaluation of mode parameters (frequency and splitting magnitude). Statistical reliability of the detection is estimated;the parameters of the Slichter mode and the corresponding density jump between the inner and outer core of the Earth are determined.

关键词： Earth's core Earth free oscillations Slichter mode laser interferometer strainmeter asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

On PTAS for the Geometric Maximum Connected k-Factor Problem 1

引用

10th International Conference on Optimization and Applications (OPTIMA)

作者： Gimadi, Edward Rykov, Ivan Tsidulko, Oxana Sobolev Inst Math 4 Acad Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ Dept Mech & Math 1 Pirogova St Novosibirsk 630090 Russia

ISBN: (数字)9783030386030

ISBN: (纸本)9783030386030;9783030386023

We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a graph correspond to a set of points in a normed space Rd and the weight of an edge is the distance between its endpoints. The k-CFP is a natural generalization of the well-known Traveling Salesman Problem, which is equivalent to the 2-CFP. In this paper we complement the known (1- 1/k(2))-approximation algorithm for the maximum k-CFP from [Baburin et al., 2007] with an approximation algorithm for the geometric k-CFP, that guarantees a relative error epsilon = O ( (k/n)(1/(d+2))). Together these two algorithms form an asymptotically optimal algorithm for the geometric k-CFP with an arbitrary value of k in an arbitrary normed space of fixed dimension d. Finally, the asymptotically optimal algorithm can be easily transformed into a PTAS for the considered geometric problem.

关键词： asymptotically optimal algorithm Polynomial time approximation scheme Connected k-factor problem Normed space NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

optimal sampling design for global approximation of jump diffusion stochastic differential equations

引用

STOCHASTICS-AN INTERNATIONAL JOURNAL OF PROBABILITY AND STOCHASTIC PROCESSES 2019年第2期91卷 235-264页

作者： Przybylowicz, Pawel AGH Univ Sci & Technol Fac Appl Math Krakow Poland

The paper deals with strong global approximation of stochastic differential equations (SDEs) driven by two independent processes: a nonhomogeneous Poisson process and a Wiener process. We assume that the jump and diffusion coefficients of the underlying SDE satisfy jump commutativity condition (see Chapter 6.3 in [21]). We establish the exact convergence rate of minimal errors that can be achieved by arbitrary algorithms based on a finite number of observations of the Poisson and Wiener processes. We consider classes of methods that use equidistant or nonequidistant sampling of the Poisson and Wiener processes. We provide a construction of optimal methods, based on the classical Milstein scheme, which asymptotically attain the established minimal errors. The analysis implies that methods based on nonequidistant mesh are more efficient, with respect to asymptotic constants, than those based on the equidistant mesh.

关键词： Nonhomogeneous poisson process wiener process jump commutativity condition standard information minimal strong error asymptotically optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding Maximal Independent Elements of Products of Partial Orders (The Case of Chains)

引用

Computational Mathematics and Modeling 2019年第1期30卷 7-12页

作者： Dyukova, E.V. Maslyakov, G.O. Prokof’ev, P.A. Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences Moscow Russian Federation Lomonosov Moscow State University Moscow Russian Federation Mechanical Engineering Research Institute of the Russian Academy of Sciences Moscow Russian Federation

We consider one of the central intractable problems of logical data analysis – finding maximal independent elements of partial orders (dualization of a product of partial orders). An important particular case is considered with each order a chain. If each chain is of cardinality 2, the problem involves the construction of a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form. An asymptotic expression is obtained for a typical number of maximal independent elements of products for a large number of finite chains. The derivation of such asymptotic bounds is a technically complex problem, but it is necessary for the proof of existence of asymptotically optimal algorithms for the monotone dualization problem and the generalization of this problem to chains of higher cardinality. An asymptotically optimal algorithm is described for the problem of dualization of a product of finite chains. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

关键词： asymptotically optimal algorithm dualization over products of partial orders irreducible covering of a Boolean matrix maximal independent element ordered covering of an integer matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：