Polynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph

M. Yu. Khachai   ; E. D. Neznakhina

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 4, pp. 297-311

Résumé

We study the Min-$k$-SCCP problem on a partition of a complete weighted digraph into $k$ vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known Traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly $NP$-hard and preserves intractability even in the geometric statement. For a metric special case of the problem, a new polynomial $2$-approximation algorithm is proposed. For the Euclidean Min-$2$-SCCP, a polynomial-time approximation scheme based on Arora's approach is built.

Détail

Keywords: $NP$-hard problem, polynomial-time approximation scheme (PTAS), traveling salesman problem (TSP), cycle covering of size $k$.

Bibliographie

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Papadimitriou C., “Euclidean TSP is $NP$-complete”, Theoret. Comput. Sci., 4 (1977), 237–244 | DOI | MR | Zbl

[3] Sahni S., Gonzales T., “$P$-complete approximation problems”, J. ACM, 23:3 (1976), 555–565 | DOI | MR | Zbl

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

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

[6] 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

[7] De Kort J. B. J. M., “Lower bounds for symmetric $K$-peripatetic salesman problems”, Optimization, 22:1 (1991), 113–122 | DOI | MR | Zbl

[8] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., 19, ed. C. R. Reeves, Reidel, Dordrecht, 1975, 173–178 | MR

[9] Baburin A. E., Gimadi E. Kh., “Ob asimptoticheskoi tochnosti effektivnogo algoritma resheniya zadachi $m$-PSP na maksimum v mnogomernom evklidovom prostranstve”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 12–24

[10] Gimadi E., “Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space”, Proc. Steklov Institute Math., 263, Suppl. 2, 2008, S57–S67 | DOI | MR

[11] Baburin A. E., Della Croce F., Gimadi E. K., Glazkov Y. V., Paschos V. Th., “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Appl. Mathematics, 157:9 (2009), 1988–1992 | DOI | MR | Zbl

[12] Dantzig G., Ramser H., “The truck dispatching problem”, Management Science, 6:1 (1959), 80–91 | DOI | MR | Zbl

[13] Toth P., Vigo D., The vehicle routing problem, Philadelphia, PA, 2001, 361 pp.

[14] Golden B., Raghavan S., Wassil E. (eds.), The vehicle routing problem: latest advances and new challenges, Operations Research. Computer Science Interfaces Series, 43, 2008, 591 pp. | MR

[15] Gimadi E. Kh., Kelmanov A. V., Pyatkin A. V., Khachai M. Yu., “Effektivnye algoritmy s otsenkami tochnosti dlya nekotorykh zadach poiska neskolkikh klik v polnom neorientirovannom vzveshennom grafe”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20, no. 2, 2014, 99–112

[16] Cormen T., Leiserson C., Rivest R., Stein C., Introduction to Algorithms, MIT Press, Cambridge–London, 1990, 1292 pp. | MR | Zbl

[17] Finkel R., Bentley J., “Quad trees. A data structure for retrieval on composite keys”, Acta Informatica, 4:1 (1974), 1–9 | DOI | Zbl