• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms

Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014), Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms, Theoretical Computer Science, 560, 2, p. 147-157. 10.1016/j.tcs.2014.10.039

Voir/Ouvrir
Approximating_MAX.pdf (498.0Kb)
Type
Article accepté pour publication ou publié
Date
2014
Nom de la revue
Theoretical Computer Science
Volume
560
Numéro
2
Éditeur
Elsevier
Pages
147-157
Identifiant publication
10.1016/j.tcs.2014.10.039
Métadonnées
Afficher la notice complète
Auteur(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]
Résumé (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.
Mots-clés
Exponential time algorithms; Approximation algorithms; Max SAT

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Approximating MAX SAT by moderately exponential algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    Moderate exponential time approximation and branching algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
  • Vignette de prévisualisation
    Using greediness for parameterization: the case of max and min (k, n − k)-cut 
    Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
  • Vignette de prévisualisation
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo