Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
From MaRDI portal
Cites work
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- A .699-approximation algorithm for Max-Bisection.
- A Parallel Repetition Theorem
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- An approximation algorithm for MAX-2-SAT with cardinality constraint
- Analysis of Boolean Functions
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Balanced max 2-sat might not be the hardest
- Best possible approximation algorithm for MAX SAT with cardinality constraint.
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Complexity of approximating CSP with balance/hard constraints
- Conditional Hardness for Approximate Coloring
- CSPs with global modular constraints: algorithms and hardness via polynomial representations
- Graph expansion and the unique games conjecture
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 1979498 (Why is no real title available?)
- scientific article; zbMATH DE number 2086914 (Why is no real title available?)
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Noise stability of functions with low influences: invariance and optimality
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Some optimal inapproximability results
- The complexity of global cardinality constraints
- The complexity of satisfiability problems
- The RPR2 rounding technique for semidefinite programs
Cited in
(9)- Computing densest \(k\)-subgraph with structural parameters
- Maximizing coverage while ensuring fairness: a tale of conflicting objectives
- Simultaneous max-cut is harder to approximate than max-cut
- Matroid-constrained vertex cover
- Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Optirefine: densest subgraphs and maximum cuts with k refinements
- Some results on approximability of minimum sum vertex cover
- Max-Cut with multiple cardinality constraints
This page was built for publication: Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875476)
