On the Hardness of Reoptimization

DOI10.1007/978-3-540-77566-9_5zbMath1133.68351OpenAlexW1602543479MaRDI QIDQ5448637

Tobias Mömke, Juraj Hromkovič, Hans-Joachim Böckenhauer, Peter Widmayer

Publication date: 7 March 2008

Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_5

zbMATH Keywords

approximation algorithmsinapproximabilityreoptimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

A survey on combinatorial optimization in dynamic environments, Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions, Reoptimization of parameterized problems, Reoptimizing the 0-1 knapsack problem, Reoptimization of maximum weight induced hereditary subgraph problems, Robust reoptimization of Steiner trees, Incremental list coloring of graphs, parameterized by conservation, Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications, Steiner tree reoptimization in graphs with sharpened triangle inequality, On Usefulness of Information: Framework and NFA Case, Reoptimization of NP-Hard Problems, Unnamed Item, Reoptimization of Steiner Trees, A theory and algorithms for combinatorial reoptimization, Parameterized dynamic cluster editing, Reoptimization in machine scheduling, A note on the traveling salesman reoptimization problem under vertex insertion, Parameterized Dynamic Variants of Red-Blue Dominating Set, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Knowing All Optimal Solutions Does Not Help for TSP Reoptimization, Reoptimization of the metric deadline TSP, Reoptimization of the Metric Deadline TSP, Fast reoptimization for the minimum spanning tree problem, Reoptimization of Weighted Graph and Covering Problems, Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights, Structural Properties of Hard Metric TSP Inputs, Reoptimization of the Shortest Common Superstring Problem, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, Parameterized Dynamic Cluster Editing

Cites Work

• Approximation algorithms for the TSP with sharpened triangle inequality
• Reoptimization of Steiner trees: changing the terminal set
• The Steiner problem with edge lengths 1 and 2
• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• On the complexity of postoptimality analysis of \(0/1\) programs
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• Some concepts of stability analysis in combinatorial optimization
• Worst-case analysis of a new heuristic for the travelling salesman problem
• The parameterized approximability of TSP with deadlines
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Some Examples of Difficult Traveling Salesman Problems
• Reoptimizing the traveling salesman problem
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• A Faster Algorithm for the Steiner Tree Problem
• The steiner problem in graphs
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item