Extension of NP Optimization Problems
Extension des problèmes NPO

View/ Open
Date
2019-07-19Dewey
Programmation, logiciels, organisation de donnéesSujet
Complexité; Complexité paramétrée; Approximation; Problèmes d’extension; Graphe; Parameterized complexity; Computational complexity; Approximation; Extension problems; Graph problemsCollections
Metadata
Show full item recordAuthor
Khosravian Ghadikolaei, Mehdi
Thesis supervisor
Monnot, JérômeType
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