Electronic Proceedings Article
@InProceedings
Internet-Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Kratsch, Stefan

dblp



Editor(s):

Albers, Susanne
Marion, Jean-Yves

dblp
dblp

Not MPII Editor(s):

Albers, Susanne
Marion, Jean-Yves

BibTeX cite key*:

Kratsch2008

Title, Conference

Title*:

Polynomial Kernelizations For MIN F+Pi1 And MAX NP

Booktitle*:

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)

Event Address*:

Freiburg, Germany

URL of the conference:

stacs2009.informatik.uni-freiburg.de/

Event Date*:
(no longer used):


URL for downloading the paper:

http://drops.dagstuhl.de/opus/volltexte/2009/1851

Event Start Date:

26 February 2009

Event End Date:

28 February 2009

Language:

English

Organization:


Publisher

Publisher's Name:

LZI

Publisher's URL:

http://www.dagstuhl.de

Address*:

Dagstuhl, Germany

Type:


Vol, No, pp., Year

Series:

Leibniz International Proceedings in Informatics

Volume:

3

Number:


Month:

March

Pages:

601-612



Sequence Number:


Year*:

2009

ISBN/ISSN:

978-3-939897-09-5


10.4230/LIPIcs.STACS.2009.1851



Abstract, Links, ©

URL for Reference:


Note:


(LaTeX) Abstract:

The relation of constant-factor approximability to fixed-parameter tractability and kernelization is a long-standing open question. We prove that two large classes of constant-factor approximable problems, namely~$\textsc{MIN F}^+\Pi_1$ and~$\textsc{MAX NP}$, including the well-known subclass~$\textsc{MAX SNP}$, admit polynomial kernelizations for their natural decision versions. This extends results of Cai and Chen (JCSS 1997), stating that the standard parameterizations of problems in~$\textsc{MAX SNP}$ and~$\textsc{MIN F}^+\Pi_1$ are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al.\ ICALP 2008).

URL for the Abstract:




Tags, Categories, Keywords:

Parameterized Complexity, Kernelization, Approximation Algorithms

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:

URN: urn:nbn:de:0030-drops-18511

Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@INPROCEEDINGS{Kratsch2008,
AUTHOR = {Kratsch, Stefan},
EDITOR = {Albers, Susanne and Marion, Jean-Yves},
TITLE = {Polynomial Kernelizations For {MIN} {F+Pi1} And {MAX} {NP}},
BOOKTITLE = {Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)},
PUBLISHER = {LZI},
YEAR = {2009},
VOLUME = {3},
PAGES = {601--612},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {Freiburg, Germany},
MONTH = {March},
ISBN = {978-3-939897-09-5},
ISBN = {1868-8969},
DOI = {10.4230/LIPIcs.STACS.2009.1851},
}


Entry last modified by Anja Becker, 03/09/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/12/2009 09:25:40 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
08.03.2010 14:17:35
08.03.2010 14:16:52
08.03.2010 14:15:35
08.03.2010 14:14:15
03/26/2009 09:40:59 AM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section