License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25011
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2501/
Go to the corresponding Portal

Demaine, Erik D. ; Hajiaghayi, MohammadTaghi ; Marx, Dániel

09511 Executive Summary -- Parameterized complexity and approximation algorithms

pdf-format:
Document 1.pdf (56 KB)

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.

BibTeX - Entry

@InProceedings{demaine_et_al:DSP:2010:2501,
  author =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx},
  title =	{09511 Executive Summary -- Parameterized complexity and approximation algorithms},
  booktitle =	{Parameterized complexity and approximation algorithms},
  year =	{2010},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx},
  number =	{09511},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2501},
  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

DROPS-Home | Fulltext Search | Imprint Published by LZI