Reoptimization of the Metric Deadline TSP

DOI10.1007/978-3-540-85238-4_12MaRDI QIDQ3599123zbMATH OpenOpenAlexFDO

Authors Dennis Komm, Hans-Joachim Böckenhauer

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Reoptimization of the metric deadline TSP
• Approximation hardness of deadline-TSP reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of minimum and maximum traveling salesman's tours
• On the Hardness of Reoptimization

Cites work

• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• 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
• On the Hardness of Reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of Steiner Trees
• Reoptimization of Steiner trees: changing the terminal set
• Reoptimizing the traveling salesman problem
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Simple and fast reoptimizations for the Steiner tree problem
• 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

(15)

• Approximation hardness of deadline-TSP reoptimization
• Reoptimization of minimum and maximum traveling salesman's tours
• Reoptimization of the metric deadline TSP
• Reoptimization of Minimum Latency problem
• Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications
• The parameterized approximability of TSP with deadlines
• New reoptimization techniques applied to Steiner tree problem
• Knowing all optimal solutions does not help for TSP reoptimization
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
• Reoptimization of the Shortest Common Superstring Problem
• Steiner tree reoptimization in graphs with sharpened triangle inequality
• A note on the traveling salesman reoptimization problem under vertex insertion
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Deadline TSP
• Reoptimization of the shortest common superstring problem

This page was built for publication: Reoptimization of the Metric Deadline TSP

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