Complexity of approximating CSP with balance/hard constraints

DOI10.1007/S00224-015-9638-0zbMATH Open1350.68142OpenAlexW791130099MaRDI QIDQ315529FDOQ315529

Authors Venkatesan Guruswami, Euiwoong Lee 

Publication date 21 September 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-015-9638-0

zbMATH Keywords

approximation algorithmscomplexity dichotomyconstraint satisfaction problemshardness of approximationunique games hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Complexity of approximating CSP with balance / hard constraints
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Hard constraint satisfaction problems have hard gaps at location 1
• scientific article; zbMATH DE number 2019637
• The approximability of constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• scientific article; zbMATH DE number 1754595 (Why is no real title available?)
• scientific article; zbMATH DE number 1762086 (Why is no real title available?)
• scientific article; zbMATH DE number 1775443 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• A .699-approximation algorithm for Max-Bisection.
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximation and Online Algorithms
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• Complexity of approximating CSP with balance / hard constraints
• Hardness of vertex deletion and project scheduling
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Inapproximability of vertex cover and independent set in bounded degree graphs
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Noise stability of functions with low influences: invariance and optimality
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimization, approximation, and complexity classes
• Robust satisfiability for CSPs: hardness and algorithmic results
• Some optimal inapproximability results
• The approximability of constraint satisfaction problems
• The complexity of satisfiability problems
• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(8)

• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Balanced max 2-sat might not be the hardest
• Complexity of approximating CSP with balance / hard constraints
• A characterization of approximability for biased CSPs
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Towards a characterization of constant-factor approximable finite-valued CSPs
• The balance problem of min-max systems is co-nNP hard
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

This page was built for publication: Complexity of approximating CSP with balance/hard constraints

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