• 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

On Subexponential and FPT-time Inapproximability

Thumbnail
Date
2013
Collection title
Lecture Notes in Computer Science
Collection Id
8246
Link to item file
http://arxiv.org/abs/1211.6656v1
Dewey
Recherche opérationnelle
Sujet
algorithms design; Independent set
DOI
http://dx.doi.org/10.1007/978-3-319-03898-8_6
Conference name
8th International Symposium, IPEC 2013
Conference date
09-2013
Conference city
Nice
Conference country
France
Book title
Parameterized and Exact Computation 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers
Author
Szeider, Stefan; Gutin, Gregory
Publisher
Springer
Publisher city
Berlin
Year
2013
ISBN
978-3-319-03897-1
Book URL
http://dx.doi.org/10.1007/978-3-319-03898-8
URI
https://basepub.dauphine.fr/handle/123456789/9735
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]
Bonnet, Édouard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
54-65
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 these different frameworks. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this article, we provide new insights to this question using two complementary approaches; the former makes a strong link between the linear PCP conjecture and inapproximability; the latter builds a class of equivalent problems under approximation in subexponential time.

  • 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.