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.