Constant-factor approximations for capacitated arc routing without triangle inequality

DOI10.1016/J.ORL.2014.05.002zbMath1408.90044arXiv1404.3660OpenAlexW1971353928MaRDI QIDQ1785236

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

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.3660

zbMATH Keywords

vehicle routingNP-hard problempolynomial-time approximationChinese postmanrural postman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06)

Related Items (8)

On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ An updated annotated bibliography on arc routing problems ⋮ Approximation algorithms for some extensions of the maximum profit routing problem

Cites Work

• Unnamed Item
• The Design of Approximation Algorithms
• An Approximation Algorithm for the Capacitated Arc Routing Problem
• A Decade of Capacitated Arc Routing
• Capacitated arc routing problems
• P-Complete Approximation Problems
• On general routing problems
• Matching, Euler tours and the Chinese postman
• Bounds for the general capacitated routing problem

This page was built for publication: Constant-factor approximations for capacitated arc routing without triangle inequality