Reoptimization of the Metric Deadline TSP

DOI10.1007/978-3-540-85238-4_12zbMath1173.90505OpenAlexW2215275723MaRDI QIDQ3599123

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

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

Related Items (6)

Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Reoptimization of the shortest common superstring problem ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ New Reoptimization Techniques applied to Steiner Tree Problem

Cites Work

• Reoptimization of Steiner trees: changing the terminal set
• 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 Steiner Trees
• Reoptimizing the traveling salesman problem
• On the Hardness of Reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• On the Approximation Hardness of Some Generalizations of TSP
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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