Sherali-Adams Relaxations for Valued CSPs
From MaRDI portal
Publication:3448860
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
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
Unnamed Item, The Complexity of Valued CSPs, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, The Complexity of General-Valued CSPs, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Super-reparametrizations of weighted CSPs: properties and optimization perspective, On planar valued CSPs, Necessary Conditions for Tractability of Valued CSPs
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