Approximation hardness of deadline-TSP reoptimization

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

zbMATH Keywords

approximation algorithmsinapproximabilityreoptimizationTSP with deadlines

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (4)

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

This page was built for publication: Approximation hardness of deadline-TSP reoptimization