An approximation algorithm for the general routing problem

DOI10.1016/0020-0190(92)90161-NzbMath0764.68074OpenAlexW2042574814WikidataQ126409363 ScholiaQ126409363MaRDI QIDQ1197996

Klaus Jansen

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90161-n

zbMATH Keywords

heuristicgeneral routing problemtriangle inequalityminimum cost cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

On residual approximation in solution extension problems ⋮ On Residual Approximation in Solution Extension Problems ⋮ Improving a constructive heuristic for the general routing problem ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ A Decade of Capacitated Arc Routing ⋮ Approximation algorithms for general cluster routing problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• P-Complete Approximation Problems
• On general routing problems
• A fundamental problem in vehicle routing
• Tight bounds for christofides' traveling salesman heuristic
• Approximation Algorithms for Some Postman Problems

This page was built for publication: An approximation algorithm for the general routing problem