• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Subexponential and FPT-time Inapproximability of Independent Set and Related Problems

Thumbnail
Date
2012
Publisher city
Paris
Collection title
Cahier du LAMSADE
Collection Id
321
Link to item file
https://hal.archives-ouvertes.fr/hal-00875483
Dewey
Programmation, logiciels, organisation des données
Sujet
algorithms
URI
https://basepub.dauphine.fr/handle/123456789/20958
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Escoffier, Bruno
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Document de travail / Working paper
Abstract (EN)
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between different approaches. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or fpt-time is a central question. In this paper, we present a strong link between the linear PCP conjecture and the inapproximability, thus partially answering this question.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.