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

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

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)

Cites Work

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

Cited In (8)

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

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)