• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • 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

Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique

NP-Hard problems : moderately exponential approximation and parameterized complexity

View/Open
2013PA090008.pdf (865.6Kb)
Date
2013-06
Pages
129
Metadata
Show full item record
Author(s)
Tourniaire, Emeric
Under the direction of
Paschos, Vangelis
Abstract (FR)
Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.
Abstract (EN)
We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.
Subjects / Keywords
Optimisation combinatoire; Algorithmes d'approximation; Théorie des graphes; Complexité; Approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée 
    Dublois, Louis (2021-07-01) Thèse
  • Thumbnail
    Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
  • Thumbnail
    Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel 
    Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Ouvrage
  • Thumbnail
    Worst-case complexity of exact algorithms for NP-hard problems 
    Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
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