Constant-factor approximations for Capacitated Arc Routing without triangle inequality

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

Research output: Contribution to journalArticlepeer-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 languageEnglish
Pages (from-to)290-292
Number of pages3
JournalOperations Research Letters
Volume42
Issue number4
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Constant-factor approximations for Capacitated Arc Routing without triangle inequality'. Together they form a unique fingerprint.

Cite this