Constant-factor approximations for Capacitated Arc Routing without triangle inequality

详细信息    查看全文

• 作者：René ; van Bevern ; ^{rene.vanbevern@tu-berlin.de" class="auth_mail} ; Sepp Hartung ^{sepp.hartung@tu-berlin.de" class="auth_mail} ; André ; Nichterlein ^{andre.nichterlein@tu-berlin.de" class="auth_mail} ; Manuel Sorge ^{manuel.sorge@tu-berlin.de" class="auth_mail}
• 关键词：NP-hard problem ; Polynomial-time approximation ; Vehicle routing ; Rural postman ; Chinese postman
• 刊名：Operations Research Letters
• 出版年：June 2014
• 年：2014
• 卷：42
• 期：4
• 页码：290-292
• 全文大小：346 K

文摘

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.