DagSemProc.09511.2.pdf
- Filesize: 55 kB
- 2 pages
Document
09511 Executive Summary – Parameterized complexity and approximation algorithms
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9511
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-03-02
Cite AsGet BibTex
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Executive Summary – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09511.2
https://doi.org/10.4230/DagSemProc.09511.2
Abstract
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.
Keywords
- Parameterized complexity
- Approximation algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads