Polynomial Kernelizations for MIN F+PI 1 and MAX NP - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Polynomial Kernelizations for MIN F+PI 1 and MAX NP

Stefan Kratsch
  • Fonction : Auteur
  • PersonId : 858008

Résumé

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).
Fichier principal
Vignette du fichier
kratsch_new.pdf (238 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00360229 , version 1 (10-02-2009)

Identifiants

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

Citer

Stefan Kratsch. Polynomial Kernelizations for MIN F+PI 1 and MAX NP. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.601-612. ⟨inria-00360229⟩

Collections

STACS2009
38 Consultations
175 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More