A PTAS for the Min-$k$-SCCP in a Euclidean space of arbitrary fixed dimension

E. D. Neznakhina

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 268-278

Résumé

We study the Min-$k$-SCCP on a partition of a complete weighted digraph into $k$ vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem (TSP) and a special case of the classical vehicle routing problem (VRP). It is known that the problem Min-$k$-SCCP is strongly $NP$-hard and preserves its intractability even in the geometric statement. For the Euclidean Min-$k$-SCCP in $\mathbb{R}^d$ with $k=O(\log n)$, we construct a polynomial-time approximation scheme, which generalizes the approach proposed earlier for the planar Min-2-SCCP. For any fixed $c>1$ the scheme finds a $(1+1/c)$-approximate solution in $O(n^{O(d)} (\log n)^{(O(\sqrt d c))^{d-1}})$ time.

Détail

Keywords: cycle covering of size $k$, traveling salesman problem (tsp), $np$-hard problem, polynomial-time approximation scheme (ptas).

Bibliographie

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

[2] Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations: Proc. Sympos., The IBM Research Symposia Series, eds. eds R.E. Miller and J.W. Thatcher, Plenum Press, New York, 1972, 85–103 | MR

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

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

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

[6] Christofides N., “Worst-case analysis of a new heuristic for the traveling salesman problem”, Proc. of Symposium on New Directions and Recent Results in Algorithms and Complexity, Academic Press, New York, 1976, 441

[7] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, “Proof verification and interactability of approximation problems”, Proc. of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, 13–22

[8] Mitchell J., “Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, $k$-MST, and related problems”, SIAM J. Comp., 28:4 (1999), 1298–1309 | DOI | MR | Zbl

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

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

[11] Khachai M.Yu., Neznakhina E.D., “Polinomialnaya priblizhennaya skhema dlya evklidovoi zadachi o tsiklovom pokrytii grafa”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20:4 (2014), 297–311 | MR

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

[13] Khachay M., Neznakhina K., “Approximation of Euclidean $k$-size cycle cover problem”, Croat. Oper. Res. Rev., 5:2 (2014), 177–188 | DOI | MR

[14] Jung H., “Über die kleinste Kugel, die eine räumliche Figur einschliesst”, J. Reine Angew. Math., 123 (1901), 241–257 | MR | Zbl

[15] Sneath P., “Computers in taxonomy”, J. Gen. Microbiol., 17 (1957), 201–226 | DOI

[16] Gower J., Ross G., “Minimum spanning trees and single linkage cluster analysis”, Appl. Statist., 18 (1969), 54–64 | DOI | MR

[17] Endryus G., Teoriya razbienii, Nauka, M., 1982, 256 pp. | MR