On the Kernelization of Global Constraints

Clément Carbonnel 1 Emmanuel Hébrard 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : Kernelization is a powerful concept from parameterized complexity theory that captures (a certain idea of) efficient polynomial-time preprocessing for hard decision problems. However, exploiting this technique in the context of constraint programming is challenging. Building on recent results for the VERTEXCOVER constraint, we introduce novel "loss-less" kernelization variants that are tailored for constraint propagation. We showcase the theoretical interest of our ideas on two constraints, VERTEXCOVER and EDGEDOMINATINGSET.
Type de document :
Communication dans un congrès
International Joint Conference on Artificial Intelligence (IJCAI 2017), Aug 2017, Melbourne, Australia. 7p., 2017
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-01670318
Contributeur : Emmanuel Hebrard <>
Soumis le : jeudi 21 décembre 2017 - 11:52:35
Dernière modification le : mercredi 28 février 2018 - 10:23:14

Fichier

ijcai2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01670318, version 1

Citation

Clément Carbonnel, Emmanuel Hébrard. On the Kernelization of Global Constraints. International Joint Conference on Artificial Intelligence (IJCAI 2017), Aug 2017, Melbourne, Australia. 7p., 2017. 〈hal-01670318〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

20