Approximation hardness of deadline-TSP reoptimization

DOI10.1016/J.TCS.2009.02.016MaRDI QIDQ1019743zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Reoptimization of the metric deadline TSP
• Reoptimization of the Metric Deadline TSP
• On the Hardness of Reoptimization
• scientific article; zbMATH DE number 5859273
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights

Cites work

• scientific article; zbMATH DE number 1114459 (Why is no real title available?)
• scientific article; zbMATH DE number 1749226 (Why is no real title available?)
• On the Approximation Hardness of Some Generalizations of TSP
• On the complexity of postoptimality analysis of 0/1 programs
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of the Metric Deadline TSP
• Reoptimizing the traveling salesman problem
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Some concepts of stability analysis in combinatorial optimization
• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• The parameterized approximability of TSP with deadlines

Cited in

(9)

• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• Heuristic reoptimization of time-extended multi-robot task allocation problems
• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• New algorithms for Steiner tree reoptimization
• New algorithms for Steiner tree reoptimization
• A note on the traveling salesman reoptimization problem under vertex insertion
• Reoptimization of the Metric Deadline TSP
• Reoptimization of the metric deadline TSP
• The parameterized approximability of TSP with deadlines

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

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