• 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

Efficient approximation by “low-complexity” exponential algorithms

Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2008), Efficient approximation by “low-complexity” exponential algorithms. https://basepub.dauphine.fr/handle/123456789/6009

View/Open
cahier_271.pdf (493.4Kb)
Type
Document de travail / Working paper
Date
2008
Publisher
Université Paris-Dauphine
Series title
Cahiers du LAMSADE
Published in
Paris
Pages
26
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bourgeois, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper proposes a way to bring together two seemingly “foreign” domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achieving ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We then apply these ideas to two famous combinatorial optimization problems, namely, the max independent set and the min vertex cover, as well as to some other problems mainly linked to max independent set by simple approximation preserving reductions.
Subjects / Keywords
polynomial approximation; NP-hard problems; min vertex cover; max independent set

Related items

Showing items related by title and author.

  • Thumbnail
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
  • Thumbnail
    Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
  • Thumbnail
    Approximation of MIN COLORING by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) 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
    Exponential approximation schemata for some network design problems 
    Boria, Nicolas; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2013) Article accepté pour publication ou publié
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