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

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.

Keywords: cycle cover, Max TSP, polyhedral metric, optimal solution, polynomial-time algorithm

The paper was received by the Editorial Office on May 8, 2018.

Funding Agency: This work was supported by the Russian Science Foundation (project no. 16-11-10041).

Vladimir Vladimirovich Shenmaier, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics SB RAS, Novosibirsk, 630090 Russia, e-mail: shenmaier@mail.ru


1.   Serdyukov A.I. Asymptotically exact algorithm for the travelling salesman maximum problem in Euclidean space. Upravlyaemyi sistemy, 1987, vol. 27, pp. 79–87 (in Russian).

2.   Serdyukov A.I. The maximum-weight travelling salesman problem in finite-dimensional real spaces. In: Korshunov A.D. (ed.), Operations research and discrete analysis., Dordrecht: Kluwer, 1997, Ser. Mathematics and its applications, vol. 391, pp. 233–239.

3.   Shenmaier V.V. An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space. J. Appl. Ind. Math., 2011, vol. 5, no.  2, pp. 296–300. doi: 10.1134/S1990478911020177 .

4.   Barvinok A., Fekete S.P., Johnson D.S., Tamir A., Woeginger G.J., Woodroofe R. The geometric maximum traveling salesman problem. J. ACM, 2003, vol. 50, no. 5, pp 641–664. doi: 10.1145/876638.876640 .

5.   Bl$\ddot{\mathrm{a}}$ser M., Manthey B. Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 2005, vol. 42, no. 2, pp. 121–139. doi: 10.1007/s00453-004-1131-0 .

6.   Cayley A. A theorem on trees. Quart. J. Pure Appl. Math., 1889, vol. 23, pp. 376–378.

7.   Engebretsen L., Karpinski M. TSP with bounded metrics. J. Comp. System Sci., 2006, vol. 72, no. 4, pp. 509–546. doi: 10.1016/j.jcss.2005.12.001 .

8.   Kaplan H., Lewenstein M., Shafrir N., Sviridenko M. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM, 2005, vol. 52, no. 4, pp. 602–626. doi: 10.1145/1082036.1082041 .

9.   Lawler E.L., Lenstra J.K., Rinnoy Kan A.H.G., Shmoys D.B. The traveling salesman problem: a guided tour of combinatorial optimization. N Y: Wiley, 1985, 465 p. ISBN: 0-471-90413-9 .

10.   Manthey B. On approximating restricted cycle covers. In: Erlebach T., Persinao G. (eds), Proc. 3rd Workshop on Approximation and Online Algorithms. WAOA 2005. Lecture Notes in Computer Science, vol. 3879. Berlin: Springer, 2006, pp. 282–295. doi: 10.1007/11671411_22 .

11.   Paluch K., Mucha M., MИadry A. A 7/9-approximation algorithm for the maximum traveling salesman problem. In: Dinur I., Jansen K., Naor J., Rolim J. (eds), Proc. 12th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2009). Lecture Notes in Computer Science, vol. 5687. Berlin: Springer, 2009, pp. 298–311. doi: 10.1007/978-3-642-03685-9_23 .

12.   Shenmaier V.V. Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP. Discrete Appl. Math., 2014, vol. 163, part 2, pp. 214–219. doi: 10.1016/j.dam.2012.09.007 .

13.   Shenmaier V.V. Complexity and approximation of the smallest k-enclosing ball problem. European J. Combinatorics, 2015, vol. 48, no. C, pp. 81–87. doi: 10.1016/j.ejc.2015.02.011 .

14.   Zemel E. An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Inf. Proc. Lett., 1984, vol. 18, no. 3, pp. 123–128. doi: 10.1016/0020-0190(84)90014-0 .