## René van Bevern, Sepp Hartung, André Nichterlein, and Manuel Sorge.
Constant-factor approximations for capacitated arc routing without
triangle inequality.
*Operations Research Letters*, 42(4):290–292, 2014.

Abstract Given an undirected graph with edge costs and
edge demands, the Capacitated Arc Routing problem
(CARP) asks for minimum-cost routes for equal-capacity
vehicles so as to satisfy all demands. Constant-factor
polynomial-time approximation algorithms were proposed
for CARP with triangle inequality, while CARP was
claimed to be NP-hard to approximate within any
constant factor in general. Correcting this claim, we
show that any factor α approximation for CARP with
triangle inequality yields a factor α approximation
for the general CARP.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*