• 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

Approximating MAX SAT by moderately exponential algorithms

Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Approximating MAX SAT by moderately exponential algorithms, in Li, Angsheng, Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings, Springer : Berlin Heidelberg, p. 622. 10.1007/978-3-642-29952-0_23

View/Open
cahier304.PDF (254.5Kb)
Type
Communication / Conférence
Date
2012
Conference title
9th Annual Conference on Theory and Applications of Models of Computation , TAMC 2012
Conference date
2012-05
Conference city
Beijing
Conference country
China
Book title
Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings
Book author
Li, Angsheng
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-29951-3
Pages
622
Publication identifier
10.1007/978-3-642-29952-0_23
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]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We study approximation of the max sat problem by moderately exponential algorithms.The general goal of the issue of moderately exponential approximation is to catch-up onpolynomial inapproximability, by providing algorithms achieving, with worst-case runningtimes importantly smaller than those needed for exact computation, approximation ratiosunachievable in polynomial time. We develop several approximation techniques that can beapplied to max sat in order to get approximation ratios arbitrarily close to 1.
Subjects / Keywords
max sat problem; moderately exponential algorithms; moderately exponential approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) 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
    Moderate exponential time approximation and branching algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
  • 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
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