On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems

DOI10.1007/S10559-011-9319-1MaRDI QIDQ464901zbMATHOpenAlexFDO

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

zbMATH Keywords

polynomial-time approximation schemereoptimization\(r\)-approximation algorithm

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

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

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Complexity of Scheduling under Precedence Constraints
• Non deterministic polynomial optimization problems and their approximations
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
• Reoptimizing the traveling salesman problem
• Simple and fast reoptimizations for the Steiner tree problem

Cited in

(10)

• Reoptimization under vertex insertion: max \(P_{k}\)-free subgraph and max planar subgraph
• Reoptimization of set covering problems
• Reoptimization of parameterized problems
• The complexity of approximation reoptimization algorithms for discrete optimization
• A theory and algorithms for combinatorial reoptimization
• A theory and algorithms for combinatorial reoptimization
• Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
• Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
• On the Hardness of Reoptimization with Multiple Given Solutions
• Reoptimization of max \(k\)-cover: approximation ratio threshold

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)