TY - GEN
T1 - Approximation algorithms for mixed, windy, and capacitated arc routing problems
AU - Van Bevern, René
AU - Komusiewicz, Christian
AU - Sorge, Manuel
PY - 2015/9/1
Y1 - 2015/9/1
N2 - 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.
AB - 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.
KW - Chinese Postman
KW - Combinatorial optimization
KW - NPhard problem
KW - Parameterized algorithm
KW - Rural Postman
KW - Transportation
KW - Vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=84946089718&partnerID=8YFLogxK
UR - https://elibrary.ru/item.asp?id=24968474
U2 - 10.4230/OASIcs.ATMOS.2015.130
DO - 10.4230/OASIcs.ATMOS.2015.130
M3 - Conference contribution
AN - SCOPUS:84946089718
T3 - OpenAccess Series in Informatics
SP - 130
EP - 143
BT - 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
A2 - Schmidt, Marie
A2 - Italiano, Giuseppe F.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
Y2 - 17 September 2015
ER -