Improved approximations for TSP with simple precedence constraints

DOI10.1016/J.JDA.2013.04.002zbMath1334.90136OpenAlexW2116948045MaRDI QIDQ396660

Monika Steinová, Hans-Joachim Böckenhauer, Tobias Mömke

Publication date: 13 August 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.04.002

zbMATH Keywords

approximationtraveling salesman problemrelaxed triangle inequalityordered TSP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

On residual approximation in solution extension problems ⋮ A hybrid algorithm for the vehicle routing problem with and/or precedence constraints and time windows ⋮ Improved approximations for ordered TSP on near-metric graphs

Cites Work

• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• The traveling salesman problem and its variations.
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• P-Complete Approximation Problems
• On the Approximation Hardness of Some Generalizations of TSP

This page was built for publication: Improved approximations for TSP with simple precedence constraints