On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
DOI10.1007/S10559-011-9319-1zbMATH Open1298.68103OpenAlexW2027146650MaRDI QIDQ464901FDOQ464901
Authors: Victor A. Mikhailyuk 
Publication date: 30 October 2014
Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10559-011-9319-1
Recommendations
- The complexity of approximation reoptimization algorithms for discrete optimization
- Approximation algorithms for discrete polynomial optimization
- Complexity and approximation in reoptimization
- Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- The scheme complexity of discrete optimization
- Reoptimization of parameterized problems
- On the Hardness of Reoptimization with Multiple Given Solutions
- On the optimality of pseudo-polynomial algorithms for integer programming
- On the optimality of pseudo-polynomial algorithms for integer programming
Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- Complexity of Scheduling under Precedence Constraints
- Simple and fast reoptimizations for the Steiner tree problem
- Reoptimizing the traveling salesman problem
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
- Non deterministic polynomial optimization problems and their approximations
Cited In (7)
- Reoptimization of max \(k\)-cover: approximation ratio threshold
- On the Hardness of Reoptimization with Multiple Given Solutions
- Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
- Reoptimization of set covering problems
- Reoptimization under vertex insertion: max \(P_{k}\)-free subgraph and max planar subgraph
- Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
- A theory and algorithms for combinatorial reoptimization
This page was built for publication: On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464901)
