An overview on polynomial approximation of NPhard problems
Paschos, Vangelis (2009), An overview on polynomial approximation of NPhard problems, Yugoslav Journal of Operations Research, 19, 1, p. 340
View/Open
Type
Article accepté pour publication ou publiéDate
2009Journal name
Yugoslav Journal of Operations ResearchVolume
19Number
1Pages
340
Metadata
Show full item recordAuthor(s)
Paschos, VangelisAbstract (EN)
The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NPhard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a tradeoff 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 NPhard problems, the polynomial approximation algorithms aim at solving a given NPhard 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 NPhard 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 NPhard 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.Subjects / Keywords
Approximation algorithms; Computational complexityRelated items
Showing items related by title and author.

Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage

Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage

Monnot, Jérôme (2002) Article accepté pour publication ou publié

Tourniaire, Emeric (201306)

Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Ouvrage