Show simple item record

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

Positive and Negative Results in Approximation and Parameterized Complexity

dc.contributor.advisorPaschos, Vangelis T.
dc.contributor.advisorEscoffier, Bruno
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822		*
dc.date.accessioned2015-01-12T08:38:04Z
dc.date.available2015-01-12T08:38:04Z
dc.date.issued2014-11
dc.identifierhttp://basepub.dauphine.fr/theses/2014PA090040
dc.identifier
dc.identifierhttp://www.theses.fr/2014PA090040
dc.identifier2014PA090040
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14503
dc.description.abstractfrDe 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.en
dc.languageen
dc.language.isoenen
dc.subjectProblèmes difficilesen
dc.subjectComplexité paramétréeen
dc.subjectApproximationen
dc.subjectSparsificationen
dc.subjectHard problemsen
dc.subjectParameterized complexityen
dc.subject.ddc511.4en
dc.titleRésultats Positifs et Négatifs en Approximation et Complexité Paramétréefr
dc.titlePositive and Negative Results in Approximation and Parameterized Complexityen
dc.typeThèseen
dc.subject.classificationrameauComplexité de calcul (informatique)
dc.subject.classificationrameauBridge (jeu)
dc.subject.classificationrameauAlgorithmes d'approximation
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenSeveral 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.en
dc.identifier.citationpages156en
dc.identifier.theseid2014PA090040en
dc.subject.ddclabelApproximation et développement en sérieen
dc.rights.intranetnonen
hal.author.functionaut


Files in this item

Thumbnail
Name:
2014PA090040.pdf
Size:
2.040Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record