On the Hardness of Reoptimization with Multiple Given Solutions

DOI10.3233/FI-2011-528MaRDI QIDQ3100925zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Andreas Sprock, Hans-Joachim Böckenhauer

Publication date 22 November 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-528

zbMATH Keywords

TSPhardnessSteiner treereoptimizationmultiple given solution

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the Hardness of Reoptimization
• Reoptimization of NP-Hard Problems
• Complexity and approximation in reoptimization
• Reoptimization of parameterized problems
• The complexity of approximation reoptimization algorithms for discrete optimization
• On the complexity of solution extension of optimization problems
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• Approximability and Hardness in Multi-objective Optimization
• A theory and algorithms for combinatorial reoptimization

Cited in

(10)

• Complexity and approximation in reoptimization
• New algorithms for Steiner tree reoptimization
• New algorithms for Steiner tree reoptimization
• Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• On the Hardness of Reoptimization
• Reoptimization in machine scheduling
• Reoptimization of NP-Hard Problems
• Knowing all optimal solutions does not help for TSP reoptimization
• Reoptimization of maximum weight induced hereditary subgraph problems

This page was built for publication: On the Hardness of Reoptimization with Multiple Given Solutions

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