Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Limits of SDP Relaxations for General-Valued CSPs

The Limits of SDP Relaxations for General-Valued CSPs It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy, (2) any instance of VCSP(Γ) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy, and (3) the support of Γ satisfies the “bounded width condition” (i.e., it contains weak near-unanimity operations of all arities). We show that if the support of Γ violates the bounded width condition then not only is VCSP(Γ) not solved by a constant level of the Sherali-Adams LP hierarchy, but it also requires linear levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Γ corresponding to linear equations in an Abelian group, this result follows from existing work on inapproximability of Max-CSPs. By a breakthrough result of Lee, Raghavendra, and Steurer [STOC’15], our result implies that for any Γ whose support violates the bounded width condition no SDP relaxation of polynomial size solves VCSP(Γ). We establish our result by proving that various reductions preserve exact solvability by the Lasserre SDP hierarchy (up to a constant factor in the level of the hierarchy). Our results hold for general-valued constraint languages (i.e., sets of functions on a fixed finite domain that take on rational or infinite values) and thus also hold in notable special cases of { 0, ∞ }-valued languages (CSPs), {0, 1}-valued languages (Min-CSPs/Max-CSPs), and Q-valued languages (finite-valued CSPs). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

The Limits of SDP Relaxations for General-Valued CSPs

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-limits-of-sdp-relaxations-for-general-valued-csps-r0xb0grGia
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3201777
Publisher site
See Article on Publisher Site

Abstract

It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy, (2) any instance of VCSP(Γ) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy, and (3) the support of Γ satisfies the “bounded width condition” (i.e., it contains weak near-unanimity operations of all arities). We show that if the support of Γ violates the bounded width condition then not only is VCSP(Γ) not solved by a constant level of the Sherali-Adams LP hierarchy, but it also requires linear levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Γ corresponding to linear equations in an Abelian group, this result follows from existing work on inapproximability of Max-CSPs. By a breakthrough result of Lee, Raghavendra, and Steurer [STOC’15], our result implies that for any Γ whose support violates the bounded width condition no SDP relaxation of polynomial size solves VCSP(Γ). We establish our result by proving that various reductions preserve exact solvability by the Lasserre SDP hierarchy (up to a constant factor in the level of the hierarchy). Our results hold for general-valued constraint languages (i.e., sets of functions on a fixed finite domain that take on rational or infinite values) and thus also hold in notable special cases of { 0, ∞ }-valued languages (CSPs), {0, 1}-valued languages (Min-CSPs/Max-CSPs), and Q-valued languages (finite-valued CSPs).

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 23, 2018

Keywords: Discrete optimization

References

  • Expander flows, geometric embeddings and graph partitioning
    Arora, Sanjeev; Rao, Satish; Vazirani, Umesh V.
  • Affine systems of equations and counting infinitary logic
    Atserias, Albert; Bulatov, Andrei; Dawar, Anuj
  • Proof complexity meets algebra
    Atserias, Albert; Ochremiak, Joanna
  • Constraint satisfaction problems solvable by local consistency methods
    Barto, Libor; Kozik, Marcin
  • Robustly solvable constraint satisfaction problems
    Barto, Libor; Kozik, Marcin
  • The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell)
    Barto, Libor; Kozik, Marcin; Niven, Todd
  • Constraint satisfaction problems with infinite templates
    Bodirsky, Manuel
  • A dichotomy theorem for constraint satisfaction problems on a 3-element set
    Bulatov, Andrei
  • A dichotomy theorem for nonuniform CSP
    Bulatov, Andrei
  • Classifying the complexity of constraints using finite algebras
    Bulatov, Andrei; Jeavons, Peter; Krokhin, Andrei
  • Complexity of conservative constraint satisfaction problems
    Bulatov, Andrei A.
  • Graphs of relational structures: Restricted types
    Bulatov, Andrei A.
  • Approximation resistance from pairwise-independent subgroups
    Chan, Siu On
  • Approximate constraint satisfaction requires large LP relaxations
    Chan, Siu On; Lee, James R.; Raghavendra, Prasad; Steurer, David
  • Integrality gaps for Sherali-Adams relaxations
    Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
  • Convex relaxations and integrality gaps
    Chlamtáč, Eden; Tulsiani, Madhur
  • An algebraic theory of complexity for discrete optimisation
    Cohen, David A.; Cooper, Martin C.; Creed, Páidí; Jeavons, Peter; Živný, Stanislav
  • Robust satisfiability for CSPs: Hardness and algorithmic results
    Dalmau, Víctor; Krokhin, Andrei A.
  • Lasserre lower bounds and definability of semidefinite programming for CSPs
    Dawar, Anuj; Wang, Pengming
  • The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
    Feder, Tomás; Vardi, Moshe Y.
  • Approximation Algorithms and Semidefinite Programming
    Gärtner, Bernd; Matoušek, Jiří
  • From weak to strong LP gaps for all CSPs
    Ghosh, Mrinal Kanti; Tulsiani, Madhur
  • Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
    Goemans, Michel X.; Williamson, David P.
  • Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
    Grigoriev, Dima
  • Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set
    Guruswami, Venkatesan; Zhou, Yuan
  • Some optimal inapproximability results
    Håstad, Johan
  • On the complexity of -coloring
    Hell, Pavol; Nešetřil, Jaroslav
  • Colouring, constraint satisfaction, and complexity
    Hell, Pavol; Nešetřil, Jaroslav
  • Closure properties of constraints
    Jeavons, Peter; Cohen, David A.; Gyssens, Marc
  • Approximate graph coloring by semidefinite programming
    Karger, David R.; Motwani, Rajeev; Sudan, Madhu
  • The complexity of general-valued CSPs
    Kolmogorov, Vladimir; Krokhin, Andrei A.; Rolínek, Michal
  • The power of linear programming for general-valued CSPs
    Kolmogorov, Vladimir; Thapper, Johan; Živný, Stanislav
  • Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
    Kothari, Pravesh K.; Meka, Raghu; Raghavendra, Prasad
  • Characterizations of several Maltsev conditions
    Kozik, Marcin; Krokhin, Andrei; Valeriote, Matt; Willard, Ross
  • Algebraic properties of valued constraint satisfaction problem
    Kozik, Marcin; Ochremiak, Joanna
  • Linear programming, width-1 CSPs, and robust satisfaction
    Kun, Gábor; O’Donnell, Ryan; Tamaki, Suguru; Yoshida, Yuichi; Zhou, Yuan
  • Bounded width problems and algebras
    Larose, Benoit; Zádori, Lázló
  • Global optimization with polynomials and the problem of moments
    Lasserre, Jean B.
  • An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
    Lasserre, Jean B.
  • A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming
    Laurent, Monique
  • Lower bounds on the size of semidefinite programming relaxations
    Lee, James R.; Raghavendra, Prasad; Steurer, David
  • Lower bounds on the size of semidefinite programming relaxations
    Lee, James R.; Raghavendra, Prasad; Steurer, David
  • Cones of matrices and set-functions and 0-1 optimization
    Lovász, László; Schrijver, Alexander
  • Existence theorems for weakly symmetric operations
    Maróti, Miklós; McKenzie, Ralph
  • Approximability and proof complexity
    O’Donnell, Ryan; Zhou, Yuan
  • Personal communication
    Raghavendra, Prasad; Steurer, David
  • The complexity of satisfiability problems
    Schaefer, Thomas J.
  • Linear level Lasserre lower bounds for certain k-CSPs
    Schoenebeck, Grant
  • A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
    Sherali, H. D.; Adams, W. P.
  • The complexity of finite-valued CSPs
    Thapper, Johan; Živný, Stanislav
  • The power of Sherali-Adams relaxations for general-valued CSPs
    Thapper, Johan; Živný, Stanislav
  • The limits of SDP relaxations for general-valued CSPs
    Thapper, Johan; Živný, Stanislav
  • CSP gaps and reductions in the Lasserre hierarchy
    Tulsiani, Madhur
  • Semidefinite programming
    Vandenberghe, Lieven; Boyd, Stephen P.
  • Approximation Algorithms
    Vazirani, Vijay V.
  • The Design of Approximation Algorithms
    Williamson, David P.; Shmoys, David B.
  • Expressing combinatorial optimization problems by linear programs
    Yannakakis, Mihalis
  • The proof of CSP dichotomy conjecture
    Zhuk, Dmitriy