Reoptimization of the metric deadline TSP

DOI10.1016/J.JDA.2009.04.001MaRDI QIDQ2266941zbMATH OpenOpenAlexFDO

Authors Hans-Joachim Böckenhauer, Dennis Komm

Publication date 26 February 2010

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2009.04.001

zbMATH Keywords

approximation algorithmsinapproximabilitymetric graphsreoptimizationdeadline TSP

Mathematics Subject Classification ID

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

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 1489999 (Why is no real title available?)
• scientific article; zbMATH DE number 1749226 (Why is no real title available?)
• Approximation hardness of deadline-TSP reoptimization
• On the Approximation Hardness of Some Generalizations of TSP
• On the Hardness of Reoptimization
• On the complexity of postoptimality analysis of 0/1 programs
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of Steiner Trees
• Reoptimization of Steiner trees: changing the terminal set
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of the Shortest Common Superstring Problem
• Reoptimizing the 0-1 knapsack problem
• 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

(21)

• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• Heuristic reoptimization of time-extended multi-robot task allocation problems
• A survey on combinatorial optimization in dynamic environments
• Reoptimization of Minimum Latency problem
• New algorithms for Steiner tree reoptimization
• Deadline TSP
• TSP race: minimizing completion time in time-sensitive applications
• New algorithms for Steiner tree reoptimization
• Reoptimization under vertex insertion: max \(P_{k}\)-free subgraph and max planar subgraph
• Reoptimization in machine scheduling
• Robust reoptimization of Steiner trees
• Deadline TSP
• Approximation hardness of deadline-TSP reoptimization
• Reoptimization of minimum and maximum traveling salesman's tours
• Reoptimization of NP-Hard Problems
• Structural properties of hard metric TSP inputs (extended abstract)
• Reoptimization of the Metric Deadline TSP
• The parameterized approximability of TSP with deadlines
• Reoptimization of maximum weight induced hereditary subgraph problems
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• scientific article; zbMATH DE number 7529517 (Why is no real title available?)

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 Q2266941)