tailieunhanh - 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 quality. | Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 3-40 DOI: AN OVERVIEW ON POLYNOMIAL APPROXIMATION OF NP-HARD PROBLEMS Vangelis Th. PASCHOS LAMSADE, CNRS UMR 7024 and University Paris-Dauphine Place du Maréchal de Lattre de Tassigny, France paschos@ Received: December 2007 / Accepted: May 2009 Abstract: 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. Keywords: Computational complexity, approximation algorithms. 1. WHAT IS POLYNOMIAL APPROXIMATION AND WHY WE DO IT? It is widely believed that no polynomial algorithm can be devised for an optimal solving of the NP-hard problems. So, several approaches, more or less satisfactory, can be followed when one tries .