A. G. Chentsov, M. Yu. Khachai, M. Yu. Khachai, “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Trudy Inst. Mat. i Mekh. UrO RAN, 21, no. 3, 2015, 309–317; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38

Trudy Instituta Matematiki i Mekhaniki UrO RAN

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2015, Volume 21, Number 3, Pages 309–317 (Mi timm1222)

This article is cited in 20 scientific papers (total in 20 papers)

An exact algorithm with linear complexity for a problem of visiting megalopolises

A. G. Chentsov^ab, M. Yu. Khachai^ba, M. Yu. Khachai^b

^a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
^b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Full-text PDF (185 kB) Citations (20)

References:

PDF

HTML

Abstract: A problem of visiting megalopolises with a fixed number of “entrances” and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.

Keywords: traveling salesman problem,

n p

$np$ -hard problem, dynamic programming, precedence relations.

Received: 11.05.2015

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, Volume 295, Issue 1, Pages 38–46
DOI: https://doi.org/10.1134/S0081543816090054

Bibliographic databases:

Document Type: Article

UDC: 519.16 + 519.85

Language: Russian

Citation: A. G. Chentsov, M. Yu. Khachai, M. Yu. Khachai, “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Trudy Inst. Mat. i Mekh. UrO RAN, 21, no. 3, 2015, 309–317; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46

Citation in format AMSBIB

\Bibitem{CheKhaKha15}

\by A.~G.~Chentsov, M.~Yu.~Khachai, M.~Yu.~Khachai

\paper An exact algorithm with linear complexity for a problem of visiting megalopolises

\serial Trudy Inst. Mat. i Mekh. UrO RAN

\yr 2015

\vol 21

\issue 3

\pages 309--317

\mathnet{http://mi.mathnet.ru/timm1222}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3468113}

\elib{https://elibrary.ru/item.asp?id=24156736}

\transl

\jour Proc. Steklov Inst. Math. (Suppl.)

\yr 2016

\vol 295

\issue , suppl. 1

\pages 38--46

\crossref{https://doi.org/10.1134/S0081543816090054}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=WOS:000394441400005}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85010430812}

Linking options:

https://www.mathnet.ru/eng/timm1222

https://www.mathnet.ru/eng/timm/v21/i3/p309

This publication is cited in the following 20 articles:

Yu. Yu. Ogorodnikov, R. A. Rudakov, D. M. Khachai, M. Yu. Khachai, “Fault-Tolerant Families of Production Plans: Mathematical Model, Computational Complexity, and Branch-and-Bound Algorithms”, Comput. Math. and Math. Phys., 64:6 (2024), 1193
Daniil Khachai, Olga Battaïa, Alexander Petunin, Michael Khachay, “Discrete cutting path problems: a general solution framework and industrial applications”, International Journal of Production Research, 2024, 1
Roman Rudakov, Yuri Ogorodnikov, Michael Khachay, Lecture Notes in Computer Science, 14766, Mathematical Optimization Theory and Operations Research, 2024, 170
Yu. Yu. Ogorodnikov, R. A. Rudakov, D. M. Khachai, M. Yu. Khachay, “Fault-tolerant families of production plans: mathematical model, computational complexity, and branch-and-bound algorithms”, Comput. Math. Math. Phys., 64:6 (2024), 1193–1210
Daniil Khachai, Ruslan Sadykov, Olga Battaia, Michael Khachay, “Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm”, European Journal of Operational Research, 309:2 (2023), 488
Roman Rudakov, Daniil Khachai, Yuri Ogorodnikov, Michael Khachay, Lecture Notes in Computer Science, 14395, Optimization and Applications, 2023, 174
M. Yu. Khachay, E. D. Neznakhina, K. V. Ryzhenko, “Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 319, suppl. 1 (2022), S140–S155
A. O. Zakharov, Yu. V. Kovalenko, “Suzhenie mnozhestva Pareto spetsialnoi struktury v diskretnykh zadachakh s dvumya kriteriyami”, Diskretn. analiz i issled. oper., 28:4 (2021), 90–116
Michael Khachay, Stanislav Ukolov, Alexander Petunin, Lecture Notes in Computer Science, 13078, Optimization and Applications, 2021, 136
Anastasiia Tavaeva, Aleksandr Petunin, Efim Polishchuk, S. Bratan, S. Roshchupkin, “Application of Multi-Contour Cutting in Algorithms for Solving the Cutting Path Problem”, MATEC Web Conf., 346 (2021), 01015
Alexander Petunin, Alexander Khalyavka, Michael Khachay, Andrei Kudriavtsev, Pavel Chentsov, Efim Polishchuk, Stanislav Ukolov, Lecture Notes in Computer Science, 12665, Pattern Recognition. ICPR International Workshops and Challenges, 2021, 227
Alexander Petunin, Efim Polishchuk, Stanislav Ukolov, Communications in Computer and Information Science, 1340, Advances in Optimization and Applications, 2020, 70
Michael Khachay, Katherine Neznakhina, “Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters”, Ann Math Artif Intell, 88:1-3 (2020), 53
Michael Khachay, Andrei Kudriavtsev, Alexander Petunin, Lecture Notes in Computer Science, 12422, Optimization and Applications, 2020, 196
A.A. Petunin, E.G. Polishchuk, S.S. Ukolov, “On the new Algorithm for Solving Continuous Cutting Problem”, IFAC-PapersOnLine, 52:13 (2019), 2320
M. Khachay, K. Neznakhina, “Polynomial time solvable subclass of the generalized traveling salesman problem on grid clusters”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 346–355
Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55
Michael Khachay, Katherine Neznakhina, Communications in Computer and Information Science, 871, Optimization Problems and Their Applications, 2018, 68
Michael Khachay, Katherine Neznakhina, Lecture Notes in Computer Science, 10627, Combinatorial Optimization and Applications, 2017, 265
M. Yu. Khachai, E. D. Neznakhina, “Approximation Schemes for the Generalized Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 97–105

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Trudy Instituta Matematiki i Mekhaniki UrO RAN

Statistics & downloads:
Abstract page:	386
Full-text PDF :	100
References:	78
First page:	23

Registration to the website

Logotypes