Sherali-Adams relaxations for valued CSPs

Abstract : We consider Sherali-Adams linear programming relaxations for solving valued constraint satisfaction problems to optimality. The utility of linear programming relaxations in this context have previously been demonstrated using the lowest possible level of this hierarchy under the name of the basic linear programming relaxation (BLP). It has been shown that valued constraint languages containing only finite-valued weighted relations are tractable if, and only if, the integrality gap of the BLP is 1. In this paper, we demonstrate that almost all of the known tractable languages with arbitrary weighted relations have an integrality gap 1 for the Sherali-Adams relaxation with parameters (2, 3). The result is closely connected to the notion of bounded relational width for the ordinary constraint satisfaction problem and its recent characterisation.
Type de document :
Communication dans un congrès
42nd International Colloquium on Automata, Languages, and Programming (ICALP-2015), 2015, Kyoto, Japan
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-01762339
Contributeur : Johan Thapper <>
Soumis le : lundi 9 avril 2018 - 22:20:29
Dernière modification le : jeudi 5 juillet 2018 - 14:46:03

Fichier

tz15icalp-preprint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01762339, version 1

Citation

Johan Thapper, Stanislav Zivny. Sherali-Adams relaxations for valued CSPs. 42nd International Colloquium on Automata, Languages, and Programming (ICALP-2015), 2015, Kyoto, Japan. 〈hal-01762339〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

8