A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. (English. Russian original) Zbl 1409.05158
Proc. Steklov Inst. Math. 289, Suppl. 1, S111-S125 (2015); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 20, No. 4, 297-311 (2014).
Summary: 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.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C22 | Signed and weighted graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
NP-hard problem; polynomial-time approximation scheme; traveling salesman problem; cycle cover of size \(k\)Software:
VRPReferences:
| [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). · Zbl 0411.68039 |
| [2] | C. Papadimitriou, “Euclidean TSP is NP-complete,” Theoret. Comput. Sci. 4, 237-244 (1977). · Zbl 0386.90057 · doi:10.1016/0304-3975(77)90012-3 |
| [3] | S. Sahni and T. Gonzalez, “<Emphasis Type=”Italic“>P-complete approximation problems,” J. Assoc. Comput. Mach. 23(3), 555-565 (1976). · Zbl 0348.90152 · doi:10.1145/321958.321975 |
| [4] | Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem, 441 (1976), New York |
| [5] | S. Arora, “Polynomial-time approximation schemes for Euclidean traveling salesman and other geometric problems,” J. Assoc. Comput. Mach. 45(5), 753-782 (1998). · Zbl 1064.90566 · doi:10.1145/290179.290180 |
| [6] | Gimadi, E. Kh; Perepelitsa, V. A., An asymptotic approach to solving the traveling salesman problem, 35-45 (1974), Novosibirsk · Zbl 0402.90096 |
| [7] | J. B. J. M. De Kort, “Lower bounds for symmetric <Emphasis Type=”Italic“>K-peripatetic salesman problems,” Optimization 22(1), 113-122 (1991). · Zbl 0717.90048 · doi:10.1080/02331939108843650 |
| [8] | Krarup, J.; Roy, B. (ed.), The peripatetic salesman and some related unsolved problems, No. 19, 173-178 (1975), Dordrecht · Zbl 0309.90059 |
| [9] | A. E. Baburin and E. Kh. Gimadi, “On the asymptotic optimality of an algorithm for solving the maximum <Emphasis Type=”Italic“>m-PSP in a multidimensional Euclidean space,” Proc. Steklov Inst. Math. 272(Suppl. 1), S1-S13 (2011). · Zbl 1230.65065 · doi:10.1134/S0081543811020015 |
| [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). · Zbl 1178.90335 · doi:10.1134/S0081543808060072 |
| [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). · Zbl 1169.90466 · doi:10.1016/j.dam.2008.06.025 |
| [12] | G. Dantzig and H. Ramser, “The truck dispatching problem,” Management Sci. 6(1), 80-91 (1959). · Zbl 0995.90560 · doi:10.1287/mnsc.6.1.80 |
| [13] | The Vehicle Routing Problem, Ed. by P. Toth and D. Vigo (SIAM, Philadelphia, 2001). |
| [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. · Zbl 1142.90004 |
| [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). · Zbl 1319.05125 · doi:10.1134/S0081543815050089 |
| [16] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, Cambridge, MA, 1990). · Zbl 1158.68538 |
| [17] | R. Finkel and J. Bentley, “Quad trees: A data structure for retrieval on composite keys,” Acta Informatica 4(1), 1-9 (1974). · Zbl 0278.68030 · doi:10.1007/BF00288933 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
