Towards a characterization of constant-factor approximable finite-valued CSPs (Q1671996): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2962988009
@@ Property / OpenAlex ID: W2962988009 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.01019
@@ Property / arXiv ID: 1610.01019 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Classifications of Boolean Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Complexity of constraints. An overview of current research themes
+Normal rank
@@ Property / cites work @@
+Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
+Normal rank
@@ Property / cites work @@
+Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
+Normal rank
@@ Property / cites work @@
+Classifying the Complexity of Constraints Using Finite Algebras
+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 @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / 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 @@
+The approximability of MAX CSP with fixed-value constraints
+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 Complexity of Finite-Valued CSPs
@@ Property / cites work: The Complexity of Finite-Valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+An Algebraic Theory of Complexity for Discrete Optimization
+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 @@
+Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for CSPs
@@ Property / cites work: Approximation Algorithms for CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+The PCP theorem by gap amplification
@@ Property / cites work: The PCP theorem by gap amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Every 2-CSP allows nontrivial approximation
@@ Property / cites work: Every 2-CSP allows nontrivial approximation / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of strong approximation resistance
+Normal rank
@@ Property / cites work @@
+O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
+Normal rank
@@ Property / cites work @@
+Complexity of approximating CSP with balance/hard constraints
+Normal rank
@@ Property / cites work @@
+Q2913811
@@ Property / cites work: Q2913811 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+Robust Satisfiability for CSPs
@@ Property / cites work: Robust Satisfiability for CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5365139
@@ Property / cites work: Q5365139 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549676
@@ Property / cites work: Q3549676 / rank @@
+Normal rank
@@ Property / cites work @@
+How to Round Any CSP
@@ Property / cites work: How to Round Any CSP / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms and Semidefinite Programming
+Normal rank
@@ Property / cites work @@
+Robust algorithms with polynomial loss for near-unanimity CSPs
+Normal rank
@@ Property / cites work @@
+Linear programming, width-1 CSPs, and robust satisfaction
+Normal rank
@@ Property / cites work @@
+Q4993594
@@ Property / cites work: Q4993594 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Valued CSPs
@@ Property / cites work: The Complexity of Valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+The Power of Linear Programming for General-Valued CSPs
+Normal rank
@@ Property / cites work @@
+Near Unanimity Constraints Have Bounded Pathwidth Duality
+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 @@
+Q3818127
@@ Property / cites work: Q3818127 / rank @@
+Normal rank
@@ Property / cites work @@
+Two new homomorphism dualities and lattice operations
+Normal rank
@@ Property / cites work @@
+Polynomial interpolation and the Chinese remainder theorem for algebraic systems
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Characterizations of several Maltsev conditions.
@@ Property / cites work: Characterizations of several Maltsev conditions. / rank @@
+Normal rank
@@ Property / cites work @@
+On algebras with many symmetric operations
@@ Property / cites work: On algebras with many symmetric operations / rank @@
+Normal rank
@@ Property / cites work @@
+Asking the Metaquestions in Constraint Tractability
+Normal rank