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.
Original language | English |
---|---|
Pages (from-to) | 290-292 |
Number of pages | 3 |
Journal | Operations Research Letters |
Volume | 42 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Externally published | Yes |
Keywords
- Chinese postman
- NP-hard problem
- Polynomial-time approximation
- Rural postman
- Vehicle routing
OECD FOS+WOS
- 5.02.PE OPERATIONS RESEARCH & MANAGEMENT SCIENCE
- 2.02.IQ ENGINEERING, ELECTRICAL & ELECTRONIC
- 1.02.EW COMPUTER SCIENCE, SOFTWARE ENGINEERING