On the Relevance of Optimal Tree Decompositions for Constraint Networks - Aix-Marseille Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

On the Relevance of Optimal Tree Decompositions for Constraint Networks

Résumé

For the study and the solving of NP-hard problems, the concept of tree decomposition is nowadays a major topic in Computer Science, in Artificial Intelligence and particularly in Constraint Programming. It appears as a promising field for the theoretical study of numerous graphical models like Bayesian Networks or (Weighted) Constraint Networks, since it can ensure, under some hypothesis, the existence of polynomial time algorithms. This concept is also used in a wide range of applications. Recently, a real improvement in the practical computation of optimal tree decompositions has been observed, allowing new promising applications of this concept in real applications. In this paper, we first aim to analyze the real relevance of such optimal decompositions. We first set that a larger set of instances are now optimally decomposable in practice but using these algorithms on a practical level still constitutes a real difficulty. In a second time, we assess the impact of such optimal decompositions for solving these instances and note a discrepancy between the empirical results and what is expected from the complexity analysis. Finally, we discuss of the next investigations which are needed on this topic.
Fichier principal
Vignette du fichier
ictai2018_final_V2.pdf (609.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01933665 , version 1 (23-11-2018)

Identifiants

  • HAL Id : hal-01933665 , version 1

Citer

Philippe Jégou, Hélène Kanso, Cyril Terrioux. On the Relevance of Optimal Tree Decompositions for Constraint Networks. Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2018, Volos, Greece. ⟨hal-01933665⟩
112 Consultations
238 Téléchargements

Partager

Gmail Facebook X LinkedIn More