• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2012), Subexponential and FPT-time Inapproximability of Independent Set and Related Problems. https://basepub.dauphine.fr/handle/123456789/20958

View/Open
cahier_321.pdf (2.139Mb)
Type
Document de travail / Working paper
Date
2012
Series title
Cahier du LAMSADE
Series number
321
Published in
Paris
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.
Subjects / Keywords
algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    On Subexponential and FPT-time Inapproximability 
    Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis; Bonnet, Édouard (2013) Communication / Conférence
  • Thumbnail
    On Subexponential and FPT-Time Inapproximability 
    Bonnet, Édouard; Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2015) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Thumbnail
    New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set 
    Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis; Xiao, Mingyu (2015) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation of MIN SAT, MAX SAT and related problems 
    Escoffier, Bruno; Paschos, Vangelis (2005) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo