Approximation hardness of deadline-TSP reoptimization
From MaRDI portal
Publication:1019743
DOI10.1016/j.tcs.2009.02.016zbMath1166.68042OpenAlexW2170739645MaRDI 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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem, Unnamed Item, A note on the traveling salesman reoptimization problem under vertex insertion, Reoptimization of the metric deadline TSP
Cites Work
- Unnamed Item
- Unnamed Item
- 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