Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.24OpenAlexW2977701101MaRDI QIDQ5875476

Aleksa Stanković, Per Austrin

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1907.04165

zbMATH Keywords

semidefinite programmingconstraint satisfaction problemsinapproximabilitymax-cutunique games conjectureglobal cardinality constraintsmax-2-sat

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Computing densest \(k\)-subgraph with structural parameters ⋮ Matroid-constrained vertex cover ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ Simultaneous max-cut is harder to approximate than max-cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of approximating CSP with balance/hard constraints
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Noise stability of functions with low influences: invariance and optimality
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Graph expansion and the unique games conjecture
• The complexity of global cardinality constraints
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• 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
• Analysis of Boolean Functions
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The RPR2 rounding technique for semidefinite programs
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• Algorithms - ESA 2003
• A .699-approximation algorithm for Max-Bisection.
• Best possible approximation algorithm for MAX SAT with cardinality constraint.

This page was built for publication: Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder