09511 Executive Summary – Parameterized complexity and approximation algorithms

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

doi:10.4230/DagSemProc.09511.2

Document

09511 Executive Summary – Parameterized complexity and approximation algorithms

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

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 9511
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2010-03-02

PDF

File

PDF

DagSemProc.09511.2.pdf

Filesize: 55 kB
2 pages

Document Identifiers

DOI: 10.4230/DagSemProc.09511.2
URN: urn:nbn:de:0030-drops-25011

Subject Classification

Keywords

Parameterized complexity
Approximation algorithms

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Erik D. Demaine

MohammadTaghi Hajiaghayi

Dániel Marx

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail