License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2015.130
URN: urn:nbn:de:0030-drops-54575
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5457/
Go to the corresponding OASIcs Volume Portal

van Bevern, René ; Komusiewicz, Christian ; Sorge, Manuel

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

pdf-format:
8.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{vanbevern_et_al:OASIcs:2015:5457,
  author =	{Ren{\'e} van Bevern and Christian Komusiewicz and Manuel Sorge},
  title =	{{Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{130--143},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5457},
  URN =		{urn:nbn:de:0030-drops-54575},
  doi =		{10.4230/OASIcs.ATMOS.2015.130},
  annote =	{Keywords: vehicle routing, transportation, Rural Postman, Chinese Postman, NP- hard problem, parameterized algorithm, combinatorial optimization}
}

Keywords: vehicle routing, transportation, Rural Postman, Chinese Postman, NP- hard problem, parameterized algorithm, combinatorial optimization
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI