## René van Bevern, Christian Komusiewicz, and Manuel Sorge.
A parameterized approximation algorithm for the mixed and windy
capacitated arc routing problem: theory and experiments.
*Networks*, 2017.
WARP 2 special issue. In press.

We prove that any polynomial-time α(n)-approximation
algorithm for the n-vertex metric asymmetric
Traveling Salesperson Problem yields a
polynomial-time O(α(C))-approximation algorithm for
the mixed and windy Capacitated Arc Routing Problem,
where C is the number of weakly connected components
in the subgraph induced by the positive-demand
arcs—a small number in many applications. In
conjunction with known results, we obtain
constant-factor approximations for C∈O(log n) and
O(log C/log log C)-approximations in general.
Experiments show that our algorithm, together with
several heuristic enhancements, outperforms many
previous polynomial-time heuristics. Finally, since
the solution quality achievable in polynomial time
appears to mainly depend on C and since C=1 in
almost all benchmark instances, we propose the Ob
benchmark set, simulating cities that are divided
into several components by a river.

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

*This file was generated by
bibtex2html 1.98.*