Document Open Access Logo

09511 Executive Summary – Parameterized complexity and approximation algorithms

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



PDF
Thumbnail PDF

File

DagSemProc.09511.2.pdf
  • Filesize: 55 kB
  • 2 pages

Document Identifiers

Author Details

Erik D. Demaine
MohammadTaghi Hajiaghayi
Dániel Marx

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail