Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-05T10:18:09Z
dc.date.available2009-10-05T10:18:09Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2113
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectComputational complexityen
dc.subject.ddc003en
dc.titleAn overview on polynomial approximation of NP-hard problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.en
dc.relation.isversionofjnlnameYugoslav Journal of Operations Research
dc.relation.isversionofjnlvol19en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2009
dc.relation.isversionofjnlpages3-40en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record