Skip to main content
Log in

A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph

  • Published:
Proceedings of the Steklov Institute of Mathematics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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).

    MATH  Google Scholar 

  2. C. Papadimitriou, “Euclidean TSP is NP-complete,” Theoret. Comput. Sci. 4, 237–244 (1977).

    Article  MATH  MathSciNet  Google Scholar 

  3. S. Sahni and T. Gonzalez, “P-complete approximation problems,” J. Assoc. Comput. Mach. 23(3), 555–565 (1976).

    Article  MATH  MathSciNet  Google Scholar 

  4. 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.

    Google Scholar 

  5. S. Arora, “Polynomial-time approximation schemes for Euclidean traveling salesman and other geometric problems,” J. Assoc. Comput. Mach. 45(5), 753–782 (1998).

    Article  MATH  Google Scholar 

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

    Google Scholar 

  7. J. B. J. M. De Kort, “Lower bounds for symmetric K-peripatetic salesman problems,” Optimization 22(1), 113–122 (1991).

    Article  MATH  MathSciNet  Google Scholar 

  8. 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.

    Google Scholar 

  9. 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).

    Article  Google Scholar 

  10. 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).

    Article  MathSciNet  Google Scholar 

  11. 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).

    Article  MATH  MathSciNet  Google Scholar 

  12. G. Dantzig and H. Ramser, “The truck dispatching problem,” Management Sci. 6(1), 80–91 (1959).

    Article  MATH  MathSciNet  Google Scholar 

  13. The Vehicle Routing Problem, Ed. by P. Toth and D. Vigo (SIAM, Philadelphia, 2001).

    Google Scholar 

  14. 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.

    Google Scholar 

  15. 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).

    Article  Google Scholar 

  16. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, Cambridge, MA, 1990).

    MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to M. Yu. Khachai.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0081543815050107

Keywords

Navigation