Hard constraint satisfaction problems have hard gaps at location 1

DOI10.1016/J.TCS.2009.05.022zbMATH Open1176.90498OpenAlexW2029110781MaRDI QIDQ837178FDOQ837178

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

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

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)

Cites Work

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

Cited In (12)

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

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)