Document Open Access Logo

Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems

Authors René van Bevern, Christian Komusiewicz, Manuel Sorge

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.130.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

René van Bevern
Christian Komusiewicz
Manuel Sorge

Cite As Get BibTex

René van Bevern, Christian Komusiewicz, and Manuel Sorge. Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 130-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.ATMOS.2015.130

Abstract

We show that any alpha(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(alpha(C))-approximation algorithms for various mixed, windy, and capacitated arc routing problems. Herein, C is the number of weakly-connected components in the subgraph induced by the positive-demand arcs, a number that can be expected to be small in applications. In conjunction with known results, we derive constant-factor approximations if C is in O(log n) and O(log(C)/log(log(C)))-approximations in general.

Subject Classification

Keywords
  • vehicle routing
  • transportation
  • Rural Postman
  • Chinese Postman
  • NP- hard problem
  • parameterized algorithm
  • combinatorial optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows - Theory, Algorithms and Applications. Prentice Hall, 1993. Google Scholar
  2. Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. In Proc. SODA'10, pages 379-389. SIAM, 2010. Google Scholar
  3. Richard Bellman. Dynamic programming treatment of the Travelling Salesman Problem. J. ACM, 9(1):61-63, 1962. Google Scholar
  4. René van Bevern, Sepp Hartung, André Nichterlein, and Manuel Sorge. Constant-factor approximations for capacitated arc routing without triangle inequality. Oper. Res. Lett., 42(4):290-292, 2014. Google Scholar
  5. René van Bevern, Rolf Niedermeier, Manuel Sorge, and Mathias Weller. Complexity of arc routing problems. In Arc Routing: Problems, Methods, and Applications. SIAM, 2014. Google Scholar
  6. Nicos Christofides. Worst case analysis of a new heuristic for the traveling salesman problem. Management Science Research Rept. 388, Carnegie-Mellon University, 1976. Google Scholar
  7. Ángel Corberán and Gilbert Laporte, editors. Arc Routing: Problems, Methods, and Applications. SIAM, 2014. Google Scholar
  8. Frederic Dorn, Hannes Moser, Rolf Niedermeier, and Mathias Weller. Efficient algorithms for Eulerian Extension and Rural Postman. SIAM J. Discrete Math., 27(1):75-94, 2013. Google Scholar
  9. Jack Edmonds. The Chinese postman problem. Oper. Res., pages B73-B77, 1975. Suppl. 1. Google Scholar
  10. Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Math. Program., 5:88-124, 1973. Google Scholar
  11. Robert W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, June 1962. Google Scholar
  12. Greg N. Frederickson. Approximation Algorithms for NP-hard Routing Problems. PhD thesis, Faculty of the Graduate School of the University of Maryland, 1977. Google Scholar
  13. Greg N. Frederickson. Approximation algorithms for some postman problems. J. ACM, 26(3):538-554, 1979. Google Scholar
  14. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation algorithms for some routing problems. SIAM J. Comput., 7(2):178-193, 1978. Google Scholar
  15. A. M. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1):23-39, 1982. Google Scholar
  16. Bruce L. Golden and Richard T. Wong. Capacitated arc routing problems. Networks, 11(3):305-315, 1981. Google Scholar
  17. Gregory Gutin, Magnus Wahlström, and Anders Yeo. Parameterized Rural Postman and Conjoining Bipartite Matching problems. Available on arXiv:1308.2599v4, 2014. Google Scholar
  18. P. Hall. On representatives of subsets. J. London Math. Soc., 10:26-30, 1935. Google Scholar
  19. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. J. SIAM, 10(1):196-210, 1962. Google Scholar
  20. Klaus Jansen. An approximation algorithm for the general routing problem. Inform. Process. Lett., 41(6):333-339, 1992. Google Scholar
  21. J. K. Lenstra and A. H. G. Rinnooy Kan. On general routing problems. Networks, 6(3):273-280, 1976. Google Scholar
  22. Balaji Raghavachari and Jeyakesavan Veerasamy. A 3/2-approximation algorithm for the Mixed Postman Problem. SIAM J. Discrete Math., 12(4):425-433, 1999. Google Scholar
  23. A. I. Serdyukov. O nekotorykh ekstremal'nykh obkhodakh v grafakh. Upravlyayemyye sistemy, 17:76-79, 1978. [On some extremal by-passes in graphs. zbMATH 0475.90080]. Google Scholar
  24. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. A new view on Rural Postman based on Eulerian Extension and Matching. J. Discrete Alg., 16:12-33, 2012. Google Scholar
  25. Sanne Wøhlk. An approximation algorithm for the Capacitated Arc Routing Problem. The Open Operational Research Journal, 2:8-12, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact