The Power of Sherali--Adams Relaxations for General-Valued CSPs (Q5348454): Difference between revisions

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