On the Approximation Hardness of Some Generalizations of TSP

DOI10.1007/11785293_19MaRDI QIDQ5757893zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Joachim Kneis, Joachim Kupke, Hans-Joachim Böckenhauer

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_19

zbMATH Keywords

approximationinapproximabilityTSP with time windows

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1754594
• scientific article; zbMATH DE number 1500530
• On the complexity of approximating TSP with neighborhoods and related problems
• TSP with bounded metrics
• The parameterized approximability of TSP with deadlines

Cited in

(20)

• Approximation hardness of deadline-TSP reoptimization
• On the approximation hardness of dense TSP and other path problems
• Approximation results for kinetic variants of TSP
• Reoptimization of the metric deadline TSP
• Complexity and approximation for traveling salesman problems with profits
• Traveling salesman problems in temporal graphs
• Traveling salesman problems in temporal graphs
• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• Reoptimization of the Metric Deadline TSP
• Improved approximations for TSP with simple precedence constraints
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• Improved approximations for ordered TSP on near-metric graphs
• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• On the Hardness of Reoptimization
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• Exponential time approximation scheme for TSP
• Scheduling on a graph with release times
• A (3/2+1/e)-approximation algorithm for ordered TSP
• Approximating prize-collecting variants of tsp

This page was built for publication: On the Approximation Hardness of Some Generalizations of TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757893)