Polynomial Kernelizations for MIN F+PI 1 and MAX NP

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~$\MINF_1$ and~$\MNP$, including the well-known subclass~$\MSNP$, 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~$\MSNP$ and~$\MINF_1$ are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al.\ ICALP 2008).
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.601-612, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360229
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 16:39:44
Dernière modification le : lundi 20 novembre 2017 - 15:14:01
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:19:07

Fichiers

kratsch_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360229, version 1
  • ARXIV : 0902.1835

Collections

Citation

Stefan Kratsch. Polynomial Kernelizations for MIN F+PI 1 and MAX NP. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.601-612, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360229〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

101