• 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

Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée

Positive and Negative Results in Approximation and Parameterized Complexity

Bonnet, Édouard (2014), Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée, doctoral thesis prepared under the supervision of Paschos, Vangelis T.; Escoffier, Bruno, Université Paris Dauphine, 156 p.

View/Open
2014PA090040.pdf (2.040Mb)
Type
Thèse
Date
2014-11
Pages
156
Metadata
Show full item record
Author(s)
Bonnet, Édouard cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Under the direction of
Paschos, Vangelis T.; Escoffier, Bruno
Abstract (FR)
De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah.
Abstract (EN)
Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah.
Subjects / Keywords
Problèmes difficiles; Complexité paramétrée; Approximation; Sparsification; Hard problems; Parameterized complexity

Related items

Showing items related by title and author.

  • Thumbnail
    Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation 
    Chopin, Morgan (2013-07) Thèse
  • Thumbnail
    Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems 
    Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
  • Thumbnail
    Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique 
    Tourniaire, Emeric (2013-06)
  • Thumbnail
    On the Parameterized Complexity of Red-Blue Points Separation 
    Bonnet, Edouard; Giannopoulos, Panos; Lampis, Michael (2017) Communication / Conférence
  • Thumbnail
    Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination 
    Katsikarelis, Ioannis (2019-12-12) Thèse
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