An overview on polynomial approximation of NP-hard problems
Paschos, Vangelis (2009), An overview on polynomial approximation of NP-hard problems, Yugoslav Journal of Operations Research, 19, 1, p. 3-40
TypeArticle accepté pour publication ou publié
Nom de la revueYugoslav Journal of Operations Research
MétadonnéesAfficher la notice complète
Résumé (EN)The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution’s quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is “close to” the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in polynomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.
Mots-clésApproximation algorithms; Computational complexity
Affichage des éléments liés par titre et auteur.