van Bevern, René
[Verfasser:in];
Komusiewicz, Christian
[Verfasser:in];
Sorge, Manuel
[Verfasser:in]
;
René van Bevern and Christian Komusiewicz and Manuel Sorge
[Mitwirkende:r]
Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.