On quadratic threshold CSPs

Abstract : A predicate P: {-1, 1}k →{0, 1} can be associated with a constraint satisfaction problem Max CSP(P). P is called ''approximation resistant'' if Max CSP(P) cannot be approximated better than the approximation obtained by choosing a random assignment, and ''approximable'' otherwise. This classification of predicates has proved to be an important and challenging open problem. Motivated by a recent result of Austrin and Mossel (Computational Complexity, 2009), we consider a natural subclass of predicates defined by signs of quadratic polynomials, including the special case of predicates defined by signs of linear forms, and supply algorithms to approximate them as follows. In the quadratic case we prove that every symmetric predicate is approximable. We introduce a new rounding algorithm for the standard semidefinite programming relaxation of Max CSP(P) for any predicate P: {-1, 1}k →{0, 1} and analyze its approximation ratio. Our rounding scheme operates by first manipulating the optimal SDP solution so that all the vectors are nearly perpendicular and then applying a form of hyperplane rounding to obtain an integral solution. The advantage of this method is that we are able to analyze the behaviour of a set of k rounded variables together as opposed to just a pair of rounded variables in most previous methods. In the linear case we prove that a predicate called ''Monarchy'' is approximable. This predicate is not amenable to our algorithm for the quadratic case, nor to other LP/SDP-based approaches we are aware of.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.205--228
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990598
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:58
Dernière modification le : mercredi 10 octobre 2018 - 21:36:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:36:09

Fichier

2117-7547-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990598, version 1

Collections

Citation

Per Austrin, Siavosh Benabbas, Avner Magen. On quadratic threshold CSPs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.205--228. 〈hal-00990598〉

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

227