Abstract
We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding 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 in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora’s approach is built.
Similar content being viewed by others
References
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Fransisco, 1979; Mir, Moscow, 1982).
C. Papadimitriou, “Euclidean TSP is NP-complete,” Theoret. Comput. Sci. 4, 237–244 (1977).
S. Sahni and T. Gonzalez, “P-complete approximation problems,” J. Assoc. Comput. Mach. 23(3), 555–565 (1976).
N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem,” in Algorithms and Complexity: New Directions and Recent Results (Academic, New York, 1976), p. 441.
S. Arora, “Polynomial-time approximation schemes for Euclidean traveling salesman and other geometric problems,” J. Assoc. Comput. Mach. 45(5), 753–782 (1998).
E. Kh. Gimadi and V. A. Perepelitsa, “An asymptotic approach to solving the traveling salesman problem,” in Control Systems: Collection of Papers (Inst. Mat. SO AN SSSR, Novosibirsk, 1974), issue 12, pp. 35–45 [in Russian].
J. B. J. M. De Kort, “Lower bounds for symmetric K-peripatetic salesman problems,” Optimization 22(1), 113–122 (1991).
J. Krarup, “The peripatetic salesman and some related unsolved problems,” in Combinatorial Programming: Methods and Applications, Ed. by B. Roy (Reidel, Dordrecht, 1975), NATO Advanced Study Institutes Series, Vol. 19, pp. 173–178.
A. E. Baburin and E. Kh. Gimadi, “On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space,” Proc. Steklov Inst. Math. 272(Suppl. 1), S1–S13 (2011).
E. Gimadi, “Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space,” Proc. Steklov Inst. Math. 263(Suppl. 1), S57–S67 (2008).
A. E. Baburin, F. Della Croce, E. K. Gimadi, Y. V. Glazkov, and V. Th. Paschos, “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2,” Discrete Appl. Math. 157(9), 1988–1992 (2009).
G. Dantzig and H. Ramser, “The truck dispatching problem,” Management Sci. 6(1), 80–91 (1959).
The Vehicle Routing Problem, Ed. by P. Toth and D. Vigo (SIAM, Philadelphia, 2001).
The Vehicle Routing Problem: Latest Advances and New Challenges, Ed. by B. Golden, S. Raghavan, and E. Wassil (Springer Science and Business Media, New York, 2008), Ser. Operations Research and Computer Science Interfaces, Vol. 43.
E. Kh. Gimadi, A. V. Kel’manov, A. V. Pyatkin, and M. Yu. Khachai, “Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph,” Proc. Steklov Inst. Math. 289(Suppl. 1), S88–S101 (2015).
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, Cambridge, MA, 1990).
R. Finkel and J. Bentley, “Quad trees: A data structure for retrieval on composite keys,” Acta Informatica 4(1), 1–9 (1974).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © M.Yu.Khachai, E.D. Neznakhina, 2014, published in Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2014, Vol. 20, No. 4.
Rights and permissions
About this article
Cite this article
Khachai, M.Y., Neznakhina, E.D. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proc. Steklov Inst. Math. 289 (Suppl 1), 111–125 (2015). https://doi.org/10.1134/S0081543815050107
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0081543815050107