Hard constraint satisfaction problems have hard gaps at location 1

DOI10.1016/J.TCS.2009.05.022MaRDI QIDQ837178zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Fredrik Kuivinen, Andrei Krokhin

Publication date 10 September 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.05.022

zbMATH Keywords

computational complexityoptimisationconstraint satisfactiondichotomyuniversal algebraapproximability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• The approximability of constraint satisfaction problems
• Complexity of approximating CSP with balance / hard constraints
• scientific article; zbMATH DE number 1559517
• The approximability of MAX CSP with fixed-value constraints

Cites work

• scientific article; zbMATH DE number 3650557 (Why is no real title available?)
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3227055 (Why is no real title available?)
• A Simple Algorithm for Mal'tsev Constraints
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for maximum generalized satisfiability problems.
• Applications of a Planar Separator Theorem
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Existence theorems for weakly symmetric operations
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Handbook of constraint programming.
• Inapproximability of combinatorial optimization problems
• Inapproximability results for equations over finite groups
• Learnability of quantified formulas.
• List homomorphisms of graphs with bounded degrees
• Maximum Constraint Satisfaction on Diamonds
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• Near-optimal algorithms for unique games
• On the Structure of Polynomial Time Reducibility
• On the algebraic structure of combinatorial problems
• On the power of unique 2-prover 1-round games
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimization, approximation, and complexity classes
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Ramanujan graphs
• Some APX-completeness results for cubic graphs
• Some optimal inapproximability results
• Supermodular functions and the complexity of MAX CSP
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The Approximability of Three-valued MAX CSP
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The PCP theorem by gap amplification
• The approximability of MAX CSP with fixed-value constraints
• The approximability of constraint satisfaction problems
• The complexity of constraint satisfaction games and QCSP
• The complexity of satisfiability problems
• The complexity of solving equations over finite groups
• The hardness of approximation: Gap location

Cited in

(12)

• PTAS for Sparse General-valued CSPs
• The power of linear programming for general-valued CSPs
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Robustly solvable constraint satisfaction problems
• \(H\)-coloring degree-bounded (acyclic) digraphs
• A characterization of hard-to-cover CSPs
• The approximability of constraint satisfaction problems
• Complexity of approximating CSP with balance/hard constraints
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• Strong partial clones and the time complexity of SAT problems
• Universal factor graphs for every NP-hard Boolean CSP

This page was built for publication: Hard constraint satisfaction problems have hard gaps at location 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q837178)