• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Extension of NP Optimization Problems

Extension des problèmes NPO

Thumbnail
View/Open
2019PSLED064.pdf (2.296Mb)
Date
2019-07-19
Dewey
Programmation, logiciels, organisation de données
Sujet
Complexité; Complexité paramétrée; Approximation; Problèmes d’extension; Graphe; Parameterized complexity; Computational complexity; Approximation; Extension problems; Graph problems
URI
https://basepub.dauphine.fr/handle/123456789/21132
Collections
  • LAMSADE : Thèses
Metadata
Show full item record
Author
Khosravian Ghadikolaei, Mehdi
Thesis supervisor
Monnot, Jérôme
Type
Thèse
Abstract (FR)
Le 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.
Abstract (EN)
The 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.

Related items

Showing items related by title, author, creator and subject.

  • On the approximation of NP-complete problems by using Boltzmann machine method. The cases of some covering and packing problems 

    Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Communication / Conférence
  • The complexity of the Pk partition problem and related problems in bipartite graphs 

    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Pk partition problem and related problems in bipartite graphs 

    Monnot, Jérôme; Toulouse, Sophie (2007) Communication / Conférence

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.