On the Hardness of Reoptimization with Multiple Given Solutions
DOI10.3233/FI-2011-528zbMATH Open1254.90185OpenAlexW2131550992MaRDI QIDQ3100925FDOQ3100925
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
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
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
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 Hardness of Reoptimization
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- 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)
