## RenĂ© van Bevern, Christian Komusiewicz, and Manuel Sorge.
Approximation algorithms for mixed, windy, and capacitated arc
routing problems.
In *Proceedings of the 15th Workshop on Algorithmic Approaches
for Transportation Modelling, Optimization, and Systems (ATMOS'15), Patras,
Greece*, volume 48 of *OpenAccess Series in Informatics (OASIcs)*, pages
130–143. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
Best paper award. The final version of this article appeared in the
WARP 2 special issue of Networks.

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.

[ bib |
DOI |
slides |
source code |
journal version |
http ]
Back

*This file was generated by
bibtex2html 1.98.*