On the Hardness of Reoptimization

DOI10.1007/978-3-540-77566-9_5MaRDI QIDQ5448637zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Tobias Mömke, 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)

Recommendations

• On the Hardness of Reoptimization with Multiple Given Solutions
• Robust reoptimization of Steiner trees
• Robust reoptimization of Steiner trees
• New algorithms for Steiner tree reoptimization
• Knowing all optimal solutions does not help for TSP reoptimization

Cites work

• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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 1500530 (Why is no real title available?)
• scientific article; zbMATH DE number 1507218 (Why is no real title available?)
• scientific article; zbMATH DE number 1749226 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• A Faster Algorithm for the Steiner Tree Problem
• Approximation algorithms for the TSP with sharpened triangle inequality
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• On the Approximation Hardness of Some Generalizations of TSP
• On the complexity of postoptimality analysis of 0/1 programs
• On the stability of approximation for Hamiltonian path problems
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of Steiner trees: changing the terminal set
• Reoptimizing the traveling salesman problem
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Some Examples of Difficult Traveling Salesman Problems
• Some concepts of stability analysis in combinatorial optimization
• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• The Steiner problem with edge lengths 1 and 2
• The parameterized approximability of TSP with deadlines
• The steiner problem in graphs
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(37)

• Fast reoptimization for the minimum spanning tree problem
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Heuristic reoptimization of time-extended multi-robot task allocation problems
• Incremental list coloring of graphs, parameterized by conservation
• A survey on combinatorial optimization in dynamic environments
• Complexity and approximation in reoptimization
• On the Hardness of Reoptimization with Multiple Given Solutions
• Parameterized Dynamic Cluster Editing
• New algorithms for Steiner tree reoptimization
• Parameterized dynamic variants of red-blue dominating set
• Parameterized dynamic cluster editing
• New algorithms for Steiner tree reoptimization
• Improved approximations for hard optimization problems via problem instance classification
• Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
• Steiner tree reoptimization in graphs with sharpened triangle inequality
• A theory and algorithms for combinatorial reoptimization
• Reoptimization of Steiner Trees
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
• A note on the traveling salesman reoptimization problem under vertex insertion
• Reoptimization in machine scheduling
• Robust reoptimization of Steiner trees
• Reoptimizing the traveling salesman problem
• Approximation hardness of deadline-TSP reoptimization
• Reoptimization of NP-Hard Problems
• Structural properties of hard metric TSP inputs (extended abstract)
• Reoptimization of the Metric Deadline TSP
• Reoptimization of parameterized problems
• Reoptimization of the Shortest Common Superstring Problem
• Reoptimization of the metric deadline TSP
• Knowing all optimal solutions does not help for TSP reoptimization
• Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications
• Reoptimizing the 0-1 knapsack problem
• A theory and algorithms for combinatorial reoptimization
• Reoptimization of maximum weight induced hereditary subgraph problems
• Finding optimal solutions with neighborly help
• On Usefulness of Information: Framework and NFA Case

This page was built for publication: On the Hardness of Reoptimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448637)