Complexity of approximating CSP with balance/hard constraints
From MaRDI portal
(Redirected from Publication:315529)
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)
