Reoptimization of the metric deadline TSP

DOI10.1016/j.jda.2009.04.001zbMath1181.90229OpenAlexW1970492377MaRDI 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

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)

Related Items (9)

A survey on combinatorial optimization in dynamic environments ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Robust reoptimization of Steiner trees ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Reoptimization of NP-Hard Problems ⋮ Unnamed Item ⋮ Reoptimization in machine scheduling ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH

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

This page was built for publication: Reoptimization of the metric deadline TSP