Approximation hardness of deadline-TSP reoptimization
From MaRDI portal
Publication:1019743
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
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