MPI-INF D1 Publications: Electronic Proceedings Article: Polynomial Kernelizations For {MIN} {F+Pi1} And {MAX} {NP}

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

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 02/12/2009 09:25:40
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

Attachment Section