Constant-factor approximations for Capacitated Arc Routing without triangle inequality

René Van Bevern; Sepp Hartung; André Nichterlein; Manuel Sorge

doi:10.1016/j.orl.2014.05.002

Constant-factor approximations for Capacitated Arc Routing without triangle inequality

René Van Bevern, Sepp Hartung, André Nichterlein, Manuel Sorge

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

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	https://doi.org/10.1016/j.orl.2014.05.002
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

Access to Document

10.1016/j.orl.2014.05.002

Link to publication in Scopus

Cite this

@article{ee8fff565feb4f18b11bfef7c151c756,

title = "Constant-factor approximations for Capacitated Arc Routing without triangle inequality",

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.",

keywords = "Chinese postman, NP-hard problem, Polynomial-time approximation, Rural postman, Vehicle routing",

author = "{Van Bevern}, Ren{\'e} and Sepp Hartung and Andr{\'e} Nichterlein and Manuel Sorge",

year = "2014",

month = jan,

day = "1",

doi = "10.1016/j.orl.2014.05.002",

language = "English",

volume = "42",

pages = "290--292",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier Science Publishing Company, Inc.",

number = "4",

}

TY - JOUR

T1 - Constant-factor approximations for Capacitated Arc Routing without triangle inequality

AU - Van Bevern, René

AU - Hartung, Sepp

AU - Nichterlein, André

AU - Sorge, Manuel

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Chinese postman

KW - NP-hard problem

KW - Polynomial-time approximation

KW - Rural postman

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84901655956&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2014.05.002

DO - 10.1016/j.orl.2014.05.002

M3 - Article

AN - SCOPUS:84901655956

VL - 42

SP - 290

EP - 292

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 4

ER -

Constant-factor approximations for Capacitated Arc Routing without triangle inequality

Abstract

Keywords

OECD FOS+WOS

Access to Document

Fingerprint

Cite this