• français
    • English
  • français 
    • 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

Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms

Thumbnail
View/Open
Approximating_MAX.pdf (498.0Kb)
Date
2014
Dewey
Programmation, logiciels, organisation des données
Sujet
Exponential time algorithms; Approximation algorithms; Max SAT
Journal issue
Theoretical Computer Science
Volume
560
Number
2
Publication date
12-2014
Article pages
147-157
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2014.10.039
URI
https://basepub.dauphine.fr/handle/123456789/20957
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]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
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 on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to max sat in order to get approximation ratios arbitrarily close to 1.

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