Constant-factor approximations for Capacitated Arc Routing without triangle inequality
arXiv:1404.3660 · doi:10.1016/j.orl.2014.05.002
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.
Cited by in corpus (5)
- A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
- On approximate data reduction for the Rural Postman Problem: Theory and experiments
- The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
- Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
- Maximum-Profit Routing Problem with Multiple Vehicles per Site