2026-07-21T14:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2501 2024-03-06T11:09:05Z ddc:004 open_access

09511 Executive Summary – Parameterized complexity and approximation algorithms Demaine, Erik D. Hajiaghayi, MohammadTaghi Marx, Dániel Parameterized complexity Approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and MohammadTaghi Hajiaghayi and Dániel Marx 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09511.2 urn:nbn:de:0030-drops-25011 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.2 eng https://creativecommons.org/licenses/by/4.0/legalcode