Skip to main content
Springer Nature Link
Log in

Approximations for the Steiner Multicycle Problem

  • Conference paper
  • First Online:
LATIN 2022: Theoretical Informatics (LATIN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13568))

Included in the following conference series:

  • 806 Accesses

  • 2 Citations

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.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 74.89
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 96.29
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

References

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

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

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

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

  6. Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report 388, Carnegie Mellon University (1976)

    Google Scholar 

  7. Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965). https://doi.org/10.4153/CJM-1965-045-4

    Article  MathSciNet  MATH  Google Scholar 

  8. Edmonds, J., Johnson, E.L.: Matchings, Euler tours and the Chinese postman problem. Math. Program. 5, 88–124 (1973)

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

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

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

  12. Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001). Preliminary version in FOCS 1998

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  14. Lovász, L., Plummer, M.D.: Matching Theory. North-Holland Mathematics Studies, vol. 121. Elsevier, Amsterdam (1986)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  19. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)

    MATH  Google Scholar 

  20. Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347–352 (1954)

    Article  MathSciNet  MATH  Google Scholar 

  21. Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04565-7

    Book  MATH  Google Scholar 

Download references

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

  1. Department of Computer Science, University of São Paulo, São Paulo, Brazil

    Cristina G. Fernandes

  2. Center for Mathematics, Computing and Cognition, Federal University of ABC, Santo André, São Paulo, Brazil

    Carla N. Lintzmayer

  3. Computer Science Department, Federal University of Minas Gerais, Belo Horizonte, Minas Gerais, Brazil

    Phablo F. S. Moura

Authors
  1. Cristina G. Fernandes
    View author publications

    Search author on:PubMed Google Scholar

  2. Carla N. Lintzmayer
    View author publications

    Search author on:PubMed Google Scholar

  3. Phablo F. S. Moura
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Carla N. Lintzmayer .

Editor information

Editors and Affiliations

  1. Universidad Nacional Autónoma de México, Mexico City, Mexico

    Armando Castañeda

  2. Centro de investigación y de Estudios Avanzados, Mexico City, Mexico

    Francisco Rodríguez-Henríquez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics