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

DOI10.1007/S10559-011-9319-1zbMath1298.68103OpenAlexW2027146650MaRDI QIDQ464901

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)

Related Items (1)

Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions

Cites Work

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

This page was built for publication: On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems