An overview on polynomial approximation of NP-hard problems
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 qualit...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Belgrade
2009-01-01
|
| Series: | Yugoslav Journal of Operations Research |
| Subjects: | |
| Online Access: | http://www.doiserbia.nb.rs/img/doi/0354-0243/2009/0354-02430901003P.pdf |
| _version_ | 1811313290245046272 |
|---|---|
| author | Paschos Vangelis Th. |
| author_facet | Paschos Vangelis Th. |
| author_sort | Paschos Vangelis Th. |
| collection | DOAJ |
| description | 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 poly-nomial 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. |
| first_indexed | 2024-04-13T10:52:09Z |
| format | Article |
| id | doaj.art-3f039054f0ef44a197d5cd1315d77234 |
| institution | Directory Open Access Journal |
| issn | 0354-0243 1820-743X |
| language | English |
| last_indexed | 2024-04-13T10:52:09Z |
| publishDate | 2009-01-01 |
| publisher | University of Belgrade |
| record_format | Article |
| series | Yugoslav Journal of Operations Research |
| spelling | doaj.art-3f039054f0ef44a197d5cd1315d772342022-12-22T02:49:38ZengUniversity of BelgradeYugoslav Journal of Operations Research0354-02431820-743X2009-01-0119134010.2298/YJOR0901003PAn overview on polynomial approximation of NP-hard problemsPaschos Vangelis Th.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 poly-nomial 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.http://www.doiserbia.nb.rs/img/doi/0354-0243/2009/0354-02430901003P.pdfcomputational complexityapproximation algorithms |
| spellingShingle | Paschos Vangelis Th. An overview on polynomial approximation of NP-hard problems Yugoslav Journal of Operations Research computational complexity approximation algorithms |
| title | An overview on polynomial approximation of NP-hard problems |
| title_full | An overview on polynomial approximation of NP-hard problems |
| title_fullStr | An overview on polynomial approximation of NP-hard problems |
| title_full_unstemmed | An overview on polynomial approximation of NP-hard problems |
| title_short | An overview on polynomial approximation of NP-hard problems |
| title_sort | overview on polynomial approximation of np hard problems |
| topic | computational complexity approximation algorithms |
| url | http://www.doiserbia.nb.rs/img/doi/0354-0243/2009/0354-02430901003P.pdf |
| work_keys_str_mv | AT paschosvangelisth anoverviewonpolynomialapproximationofnphardproblems AT paschosvangelisth overviewonpolynomialapproximationofnphardproblems |