Geodesic
An exact algorithm with linear complexity for a problem of visiting megalopolises
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 309-317 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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, $np$-hard problem, dynamic programming, precedence relations. 
@article{TIMM_2015_21_3_a30,
     author = {A. G. Chentsov and M. Yu. Khachai and M. Yu. Khachai},
     title = {An exact algorithm with linear complexity for a problem of visiting megalopolises},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {309--317},
     year = {2015},
     volume = {21},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a30/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - M. Yu. Khachai
AU  - M. Yu. Khachai
TI  - An exact algorithm with linear complexity for a problem of visiting megalopolises
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 309
EP  - 317
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a30/
LA  - ru
ID  - TIMM_2015_21_3_a30
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A M. Yu. Khachai
%A M. Yu. Khachai
%T An exact algorithm with linear complexity for a problem of visiting megalopolises
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 309-317
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a30/
%G ru
%F TIMM_2015_21_3_a30
A. G. Chentsov; M. Yu. Khachai; M. Yu. Khachai. An exact algorithm with linear complexity for a problem of visiting megalopolises. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 309-317. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a30/

[1] V.V. Korobkin, A.N. Sesekin, O.L. Tashlykov, A.G. Chentsov, Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya bezopasnosti i effektivnosti ekspluatatsii atomnykh stantsii, Novye tekhnologii, M., 2012, 234 pp.

[2] Chentsov A.G., “K voprosu o marshrutizatsii kompleksov rabot”, Vestn. Udmurt. un-ta, (Matematika, mekhanika, kompyuter. nauki), 2013, no. 1, 59–82 | Zbl

[3] Chentsov A.G., Chentsov A.A., Chentsov P.A., “Elementy dinamicheskogo programmirovaniya v ekstremalnykh zadachakh marshrutizatsii”, Problemy upravleniya, 2013, no. 5, 12–21

[4] Chentsov A.G., “Zadacha posledovatelnogo obkhoda megapolisov s usloviyami predshestvovaniya”, Avtomatika i telemekhanika, 2014, no. 4, 170–190 | MR | Zbl

[5] Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations: Proc. Sympos., eds. eds. R.E. Miller, J.W. Thatcher, Plenum, New York, 1972, 85–103 | DOI | MR

[6] Garey M., Johnson D., Computers and intractability: a guide to the theory of $NP$-completeness, A Ser. of Books in the Mathematical Sciences, W.H. Freeman and Co, San Francisco, 1979, 339 pp. | MR | Zbl

[7] Christofides N., “Worst-case analysis of a new heuristic for the traveling salesman problem”, Proc. of a Symposium on new directions and recent results in algorithms and complexity, Academic Press, New York, 1976, 441

[8] Arora S., “Polynomial-time approximation schemes for Euclidean traveling salesman and other geometric problems”, J. ACM, 45:5 (1998), 753–782 | DOI | MR | Zbl

[9] Gimadi E.Kh., Perepelitsa V.A., “Asimptoticheski tochnyi podkhod k resheniyu zadachi kommivoyazhera”, Upravlyaemye sistemy: sb. nauch. tr., 12, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 35–45 | Zbl

[10] Khachai M.Yu., Neznakhina E.D., “Approksimiruemost zadachi o minimalnom po vesu tsiklovom pokrytii grafa”, Dokl. RAN, 461:6 (2015), 644–649 | DOI | Zbl

[11] Khachai M.Yu., Neznakhina E.D., “PTAS dlya zadachi Min-k-SCCP v evklidovom prostranstve proizvolnoi fiksirovannoi razmernosti”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20:4 (2014), 297–311 | MR

[12] Bellman R., “Dynamis programming treatment of the traveling salesman problem”, J. Assoc. Comput. Mach., 9 (1962), 61–63 | DOI | MR | Zbl

[13] Held M., Karp R., “A dynamic programming approach to sequencing problems”, J. Soc. Indust. Appl. Math., 10:1 (1962), 196–210 | DOI | MR | Zbl

[14] Balas E., “New classes of efficiently solvable generalized traveling salesman problems”, Ann. Oper. Res., 86 (1999), 529–558 | DOI | MR | Zbl

[15] Balas E., Simonetti N., “Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study”, INFORMS J. Comput., 13:1 (2001), 56–75 | DOI | MR | Zbl

[16] Introduction to algorithms, 3 ed., eds. eds. T. Cormen [et al.], MIT Press, Boston, 2009, 1312 pp. | MR | Zbl

[17] Melamed I.I., Sergeev S.I., Sigal I.Kh., “Zadacha kommivoyazhera. Tochnye metody”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | MR | Zbl

[18] The traveling salesman problem: a guided tour of combinatorial optimization, eds. eds. E.L. Lawler [et al.], John Wiley Sons, New York, 1985, 476 pp. | MR | Zbl

[19] Steiner G., “On the complexity of dynamic programming for sequencing problems with precedence constraints”, Ann. Oper. Res., 26:1-4 (1990), 103–123 | DOI | MR | Zbl

[20] A.M. Grigorev, E.E. Ivanko, S.T. Knyazev, A.G. Chentsov, “Dinamicheskoe programmirovanie v obobschennoi zadache kurera, oslozhnennoi vnutrennimi rabotami”, Mekhatronika, avtomatizatsiya, upravlenie, 2012, no. 7, 14–21