Sherali-Adams Relaxations for Valued CSPs

DOI10.1007/978-3-662-47672-7_86zbMath1440.68132arXiv1502.05301MaRDI QIDQ3448860

Stanislav Živný, Johan Thapper

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C05: Linear programming

08A70: Applications of universal algebra in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization

68R07: Computational aspects of satisfiability

Related Items

The Complexity of General-Valued CSPs, The Power of Sherali--Adams Relaxations for General-Valued CSPs, On planar valued CSPs, Necessary Conditions for Tractability of Valued CSPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Bounded width problems and algebras
• Characterizations of several Maltsev conditions.
• The complexity of soft constraint satisfaction
• Combinatorial problems raised from 2-semilattices
• The collapse of the bounded width hierarchy
• Linear programming, width-1 CSPs, and robust satisfaction
• Robust Satisfiability for CSPs
• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• 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
• A Galois Connection for Valued Constraint Languages of Infinite Size
• Algebraic Properties of Valued Constraint Satisfaction Problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Power of Linear Programming for 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
• The complexity of conservative valued CSPs
• Robust satisfiability of constraint satisfaction problems
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems