2010/01/01 by Erik D. Demaine, Demaine, Erik D., MohammadTaghi Hajiaghayi +3
Computer Science · #Advanced Graph Theory Research #Approximation algorithms #Constraint Satisfaction and Optimization #Parameterized complexity
paper · doi:10.4230/dagsemproc.09511.2
openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many of the computational problems that arise in practice are optimization problems: the task is to find a solution where the cost, quality, size, profit, or some other measure is as large or small as possible. The NP-hardness of an optimization problem implies that, unless P = NP, there is no polynomial-time algorithm that finds the exact value of the optimum. Various approaches have been proposed in the literature to cope with NP-hard problems. When designing approximation algorithms, we relax the requirement that the algorithm produces an optimum solution, and our aim is to devise a polynomial-time algorithm such that the solution it produces is not necessarily optimal, but there is some worst-case bound on the solution quality.