An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles

V. V. Shenmaier

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 272-280

Résumé

A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case when the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.

Détail

Keywords: cycle cover, Max TSP, polyhedral metric
Mots-clés : optimal solution, polynomial-time algorithm.

Bibliographie

[1] Serdyukov A.I., “Asimptoticheski tochnyi algoritm dlya zadachi kommivoyazhera na maksimum v evklidovom prostranstve”, Metody tselochislennoi optimizatsii, Upravlyaemye sistemy, 27, In-t matematiki SO AN SSSR, Novosibirsk, 1987, 79–87

[2] Serdyukov A.I., “Zadacha kommivoyazhera na maksimum v konechnomernykh veschestvennykh prostranstvakh”, Diskretnyi analiz i issledovanie operatsii, 2:1 (1995), 50–56

[3] Shenmaier V.V., “Asimptoticheski tochnyi algoritm dlya zadachi kommivoyazhera na maksimum v konechnomernom normirovannom prostranstve”, Diskretnyi analiz i issledovanie operatsii, 17:4 (2010), 84–91

[4] Barvinok A., Fekete S. P., Johnson D. S., Tamir A., Woeginger G. J., Woodroofe R., “The geometric maximum traveling salesman problem”, J. ACM, 50:5 (2003), 641–664 | DOI

[5] Bl$\ddot{\mathrm{a}}$ser M., Manthey B., “Approximating maximum weight cycle covers in directed graphs with weights zero and one”, Algorithmica, 42:2 (2005), 121–139 | DOI

[6] Cayley A., “A theorem on trees”, Quart. J. Pure Appl. Math., 23 (1889), 376–378

[7] Engebretsen L., Karpinski M., “TSP with bounded metrics”, J. Comp. System Sci., 72:4 (2006), 509–546 | DOI

[8] Kaplan H., Lewenstein M., Shafrir N., Sviridenko M., “Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs”, J. ACM, 52:4 (2005), 602–626 | DOI

[9] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, N Y, 1985, 465 pp.

[10] Manthey B., “On approximating restricted cycle covers”, Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), Lecture Notes in Computer Science, 3879, Springer, Berlin, 2006, 282–295 | DOI

[11] Paluch K., Mucha M., Madry A., “A 7/9-approximation algorithm for the maximum traveling salesman problem”, Proc. 12th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2009), Lecture Notes in Computer Science, 5687, Springer, Berlin, 2009, 298–311 | DOI

[12] Shenmaier V. V., “Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP”, Discrete Appl. Math., 163:2 (2014), 214–219 | DOI

[13] Shenmaier V. V., “Complexity and approximation of the smallest k-enclosing ball problem”, European J. Combinatorics, 48:C (2015), 81–87 | DOI

[14] Zemel E., “An O(n) algorithm for the linear multiple choice knapsack problem and related problems”, Inf. Proc. Lett., 18:3 (1984), 123–128 | DOI