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

hardnessmultiple given solutionreoptimizationSteiner treeTSP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) 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)

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

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)