@inproceedings{a0a1c542ad59447f80b7200bebd463c8,
title = "Approximation algorithms for mixed, windy, and capacitated arc routing problems",
abstract = "We show that any α(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(α(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 ε O(log n) and O(log C/log log C) -approximations in general.",
keywords = "Chinese Postman, Combinatorial optimization, NPhard problem, Parameterized algorithm, Rural Postman, Transportation, Vehicle routing",
author = "{Van Bevern}, Ren{\'e} and Christian Komusiewicz and Manuel Sorge",
year = "2015",
month = sep,
day = "1",
doi = "10.4230/OASIcs.ATMOS.2015.130",
language = "English",
series = "OpenAccess Series in Informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "130--143",
editor = "Marie Schmidt and Italiano, {Giuseppe F.}",
booktitle = "15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015",
address = "Germany",
note = "15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 ; Conference date: 17-09-2015",
}