The Power of Sherali--Adams Relaxations for General-Valued CSPs

DOI10.1137/16M1079245zbMath1371.68125arXiv1606.02577MaRDI QIDQ5348454

Stanislav Živný, Johan Thapper

Publication date: 16 August 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.02577

zbMATH Keywords

linear programmingSherali-Adams hierarchyvalued constraint satisfaction problemsfractional polymorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ On a general framework for network representability in discrete optimization ⋮ On planar valued CSPs ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Proof Complexity Meets Algebra ⋮ The Complexity of Valued CSPs ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• Pseudo-Boolean optimization
• A new line of attack on the dichotomy conjecture
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• A dichotomy theorem for maximum generalized satisfiability problems.
• There are no pure relational width 2 constraint satisfaction problems
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• Affine systems of equations and counting infinitary logic
• Characterizations of several Maltsev conditions.
• The complexity of soft constraint satisfaction
• Combinatorial problems raised from 2-semilattices
• The Approximability of Constraint Satisfaction Problems
• Global Optimization with Polynomials and the Problem of Moments
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Convex Relaxations and Integrality Gaps
• Half-integrality, LP-branching, and FPT Algorithms
• Robustly Solvable Constraint Satisfaction Problems
• The collapse of the bounded width hierarchy
• Linear programming, width-1 CSPs, and robust satisfaction
• Complexity of conservative constraint satisfaction problems
• Robust Satisfiability for CSPs
• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Skew Bisubmodularity and Valued CSPs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Sherali-Adams Relaxations for Valued CSPs
• Necessary Conditions for Tractability of Valued CSPs
• The Maximum Solution Problem on Graphs
• MAX ONES Generalized to Larger Domains
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Sum-of-squares proofs and the quest toward optimal algorithms
• Graphs of relational structures
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• The Complexity of Valued CSPs
• CSP gaps and reductions in the lasserre hierarchy
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• Towards a Characterization of Constant-Factor Approximable Min CSPs
• Binarisation for Valued Constraint Satisfaction Problems
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimization
• Constraint Satisfaction Problems with Infinite Templates
• Introduction to the Maximum Solution Problem
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Discrete convexity and polynomial solvability in minimum 0-extension problems

This page was built for publication: The Power of Sherali--Adams Relaxations for General-Valued CSPs