License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/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:
09511.SWM.ExtAbstract.2501.pdf (0.05 MB)

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: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
Collection: 09511 - Parameterized complexity and approximation algorithms
Issue Date: 2010
Date of publication: 02.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI