Complexity of approximating CSP with balance/hard constraints

DOI10.1007/S00224-015-9638-0zbMath1350.68142OpenAlexW791130099MaRDI QIDQ315529

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 algorithmsconstraint satisfaction problemshardness of approximationcomplexity dichotomyunique 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)

Related Items (3)

Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hardness of approximating minimum vertex cover
• Noise stability of functions with low influences: invariance and optimality
• Optimization, approximation, and complexity classes
• Approximating minimum feedback sets and multicuts in directed graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The Approximability of Constraint Satisfaction Problems
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• Robust Satisfiability for CSPs
• Complexity of approximating CSP with balance / hard constraints
• Hardness of Vertex Deletion and Project Scheduling
• On the power of unique 2-prover 1-round games
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• Approximation and Online Algorithms
• A .699-approximation algorithm for Max-Bisection.

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