Reoptimization of the metric deadline TSP
From MaRDI portal
Publication:2266941
DOI10.1016/j.jda.2009.04.001zbMath1181.90229MaRDI QIDQ2266941
Dennis Komm, Hans-Joachim Böckenhauer
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
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Unnamed Item, Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem, Reoptimization of NP-Hard Problems, Reoptimization of maximum weight induced hereditary subgraph problems, Robust reoptimization of Steiner trees, Reoptimization in machine scheduling, REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH, A survey on combinatorial optimization in dynamic environments, Structural Properties of Hard Metric TSP Inputs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reoptimizing the 0-1 knapsack problem
- Reoptimization of Steiner trees: changing the terminal set
- Approximation hardness of deadline-TSP reoptimization
- 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
- Reoptimization of Weighted Graph and Covering Problems
- Reoptimization of the Shortest Common Superstring Problem
- 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