Abstract
The Steiner Multicycle problem consists in, given a complete graph G, a weight function \(w :E(G) \rightarrow \mathbb {Q}_+\), and a partition of V(G) into terminal sets, finding a minimum-weight collection of disjoint cycles in G such that, for every terminal set T, all vertices of T are in a same cycle of the collection. This problem, which is motivated by applications on routing problems with pickup and delivery locations, generalizes the Traveling Salesman problem (TSP) and therefore is hard to approximate in general. Using an algorithm for the Survivable Network Design problem and T-joins, we obtain a 3-approximation for its metric case, improving on the previous best 4-approximation. Furthermore, inspired by a result by Papadimitriou and Yannakakis for the \(\{1,2\}\)-TSP, we present an (11/9)-approximation for the particular case of the Steiner Multicycle in which each edge weight is 1 or 2. This algorithm can be adapted into a (7/6)-approximation when every terminal set contains at least 4 vertices.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adamaszek, A., Mnich, M., Paluch, K.: New approximation algorithms for \((1,2)\)-TSP. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 9:1–9:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.9
Arora, S.: Polynomial time approximation schemes for Euclidean Traveling Salesman and other geometric problems. J. ACM 45(5), 753–782 (1998). https://doi.org/10.1145/290179.290180
Bansal, N., Bravyi, S., Terhal, B.M.: Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs. Quant. Inf. Comput. 9(7), 701–720 (2009)
Berman, P., Karpinski, M.: \(8/7\)-approximation algorithm for \((1,2)\)-TSP. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 641–648 (2006)
Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algorithms 11(3), 19:1–19:20 (2015). https://doi.org/10.1145/2629654
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report 388, Carnegie Mellon University (1976)
Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965). https://doi.org/10.4153/CJM-1965-045-4
Edmonds, J., Johnson, E.L.: Matchings, Euler tours and the Chinese postman problem. Math. Program. 5, 88–124 (1973)
Ergun, O., Kuyzu, G., Savelsbergh, M.: Reducing truckload transportation costs through collaboration. Transp. Sci. 41(2), 206–221 (2007). https://doi.org/10.1287/trsc.1060.0169
Ergun, O., Kuyzu, G., Savelsbergh, M.: Shipper collaboration. Compute. Oper. Res. 34(6), 1551–1560 (2007). https://doi.org/10.1016/j.cor.2005.07.026. Part Special Issue: Odysseus 2003 Second International Workshop on Freight Transportation Logistics
Hartvigsen, D.: An extension of matching theory. Ph.D. thesis, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, USA (1984). https://david-hartvigsen.net/?page_id=33
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001). Preliminary version in FOCS 1998
Lintzmayer, C.N., Miyazawa, F.K., Moura, P.F.S., Xavier, E.C.: Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. Theor. Comput. Sci. 835, 134–155 (2020). https://doi.org/10.1016/j.tcs.2020.06.022
Lovász, L., Plummer, M.D.: Matching Theory. North-Holland Mathematics Studies, vol. 121. Elsevier, Amsterdam (1986)
Papadimitriou, C.H., Yannakakis, M.: The Traveling Salesman Problem with distances one and two. Math. Oper. Res. 18(1), 1–11 (1993). https://doi.org/10.1287/moor.18.1.1
Pereira, V.N.G., Felice, M.C.S., Hokama, P.H.D.B., Xavier, E.C.: The Steiner Multi Cycle Problem with applications to a collaborative truckload problem. In: 17th International Symposium on Experimental Algorithms (SEA 2018), pp. 26:1–26:13 (2018). https://doi.org/10.4230/LIPIcs.SEA.2018.26
Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563–581 (1977)
Salazar-González, J.J.: The Steiner cycle polytope. Eur. J. Oper. Res. 147(3), 671–679 (2003). https://doi.org/10.1016/S0377-2217(02)00359-4
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)
Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347–352 (1954)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04565-7
Acknowledgement
C. G. Fernandes was partially supported by the National Council for Scientific and Technological Development – CNPq (Proc. 310979/2020-0 and 423833/2018-9). C. N. Lintzmayer was partially supported by CNPq (Proc. 312026/2021-8 and 428385/2018-4). P. F. S. Moura was partially supported by the Fundação de Amparo à Pesquisa do Estado de Minas Gerais – FAPEMIG (APQ-01040-21). This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001, and by Grant #2019/13364-7, São Paulo Research Foundation (FAPESP).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Fernandes, C.G., Lintzmayer, C.N., Moura, P.F.S. (2022). Approximations for the Steiner Multicycle Problem. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-20624-5_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20623-8
Online ISBN: 978-3-031-20624-5
eBook Packages: Computer ScienceComputer Science (R0)