Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09511.2
URN: urn:nbn:de:0030-drops-25011
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2501/
Demaine, Erik D. ; Hajiaghayi, MohammadTaghi ; Marx, Dániel
09511 Executive Summary -- Parameterized complexity and approximation algorithms
| pdf-format: |
|
Abstract
Many of the computational problems that arise in practice are optimizationproblems: 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.
BibTeX - Entry
@InProceedings{demaine_et_al:DagSemProc.09511.2,
author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel},
title = {{09511 Executive Summary – Parameterized complexity and approximation algorithms}},
booktitle = {Parameterized complexity and approximation algorithms},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2010},
volume = {9511},
editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2010/2501},
URN = {urn:nbn:de:0030-drops-25011},
doi = {10.4230/DagSemProc.09511.2},
annote = {Keywords: Parameterized complexity, Approximation algorithms}
}
| Keywords: | Parameterized complexity, Approximation algorithms | |
| Seminar: | 09511 - Parameterized complexity and approximation algorithms | |
| Issue date: | 2010 | |
| Date of publication: | 02.03.2010 |
