Approximation hardness of deadline-TSP reoptimization

DOI10.1016/j.tcs.2009.02.016zbMath1166.68042MaRDI QIDQ1019743

Joachim Kneis, Joachim Kupke, Hans-Joachim Böckenhauer

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.016

zbMATH Keywords

approximation algorithms; inapproximability; reoptimization; TSP with deadlines

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Unnamed Item, Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem, A note on the traveling salesman reoptimization problem under vertex insertion, Reoptimization of the metric deadline TSP

Cites Work

• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• On the complexity of postoptimality analysis of \(0/1\) programs
• Some concepts of stability analysis in combinatorial optimization
• The parameterized approximability of TSP with deadlines
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Reoptimization of the Metric Deadline TSP
• Reoptimizing the traveling salesman problem
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• On the Approximation Hardness of Some Generalizations of TSP
• Unnamed Item
• Unnamed Item