Show simple item record

Extension des problèmes NPO

dc.contributor.advisorMonnot, Jérôme
hal.structure.identifier
dc.contributor.authorKhosravian Ghadikolaei, Mehdi*
dc.date.accessioned2020-10-21T07:51:21Z
dc.date.available2020-10-21T07:51:21Z
dc.date.issued2019-07-19
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21132
dc.description.abstractfrLe problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielle.fr
dc.language.isoen
dc.subjectComplexitéfr
dc.subjectComplexité paramétréefr
dc.subjectApproximationfr
dc.subjectProblèmes d’extensionfr
dc.subjectGraphefr
dc.subjectParameterized complexityen
dc.subjectComputational complexityen
dc.subjectApproximationen
dc.subjectExtension problemsen
dc.subjectGraph problemsen
dc.subject.ddc005.1
dc.titleExtension of NP Optimization Problemsen
dc.titleExtension des problèmes NPOfr
dc.typeThèse
dc.contributor.editoruniversityParis Sciences et Lettres
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenThe problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied.en
dc.identifier.theseid2019PSLED064
dc.subject.ddclabelProgrammation, logiciels, organisation de données
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record