Standard

Constant-factor approximations for Capacitated Arc Routing without triangle inequality. / Van Bevern, René; Hartung, Sepp; Nichterlein, André et al.

In: Operations Research Letters, Vol. 42, No. 4, 01.01.2014, p. 290-292.

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

Harvard

Van Bevern, R, Hartung, S, Nichterlein, A & Sorge, M 2014, 'Constant-factor approximations for Capacitated Arc Routing without triangle inequality', Operations Research Letters, vol. 42, no. 4, pp. 290-292. https://doi.org/10.1016/j.orl.2014.05.002

APA

Van Bevern, R., Hartung, S., Nichterlein, A., & Sorge, M. (2014). Constant-factor approximations for Capacitated Arc Routing without triangle inequality. Operations Research Letters, 42(4), 290-292. https://doi.org/10.1016/j.orl.2014.05.002

Vancouver

Van Bevern R, Hartung S, Nichterlein A, Sorge M. Constant-factor approximations for Capacitated Arc Routing without triangle inequality. Operations Research Letters. 2014 Jan 1;42(4):290-292. doi: 10.1016/j.orl.2014.05.002

Author

Van Bevern, René ; Hartung, Sepp ; Nichterlein, André et al. / Constant-factor approximations for Capacitated Arc Routing without triangle inequality. In: Operations Research Letters. 2014 ; Vol. 42, No. 4. pp. 290-292.

BibTeX

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

}

RIS

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 -

ID: 22340632