Demaine, Erik D. ;
Hajiaghayi, MohammadTaghi ;
Marx, Dániel
09511 Executive Summary  Parameterized complexity and approximation algorithms
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
NPhardness of an optimization problem implies that, unless P = NP, there is
no polynomialtime algorithm that finds the exact value of the optimum.
Various approaches have been proposed in the literature to cope with NPhard
problems. When designing approximation algorithms, we relax the requirement
that the algorithm produces an optimum solution, and our aim is to devise a
polynomialtime algorithm such that the solution it produces is not
necessarily optimal, but there is some worstcase 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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2501},
annote = {Keywords: Parameterized complexity, Approximation algorithms}
}
2010
Keywords: 

Parameterized complexity, Approximation algorithms 
Seminar: 

09511  Parameterized complexity and approximation algorithms

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 