Constant-factor approximations for Capacitated Arc Routing without triangle inequality

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

Результат исследования: Научные публикации в периодических изданияхстатья

6 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)290-292
Число страниц3
ЖурналOperations Research Letters
Том42
Номер выпуска4
DOI
СостояниеОпубликовано - 1 янв 2014
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «Constant-factor approximations for Capacitated Arc Routing without triangle inequality». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать