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.