Sherali-Adams Relaxations for Valued CSPs

DOI10.1007/978-3-662-47672-7_86zbMath1440.68132arXiv1502.05301OpenAlexW3104855793MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (8)

The Complexity of General-Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ On planar valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ The Complexity of Valued CSPs ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Unnamed Item

Cites Work

• 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
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• 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

This page was built for publication: Sherali-Adams Relaxations for Valued CSPs