A characterization of approximability for biased CSPs
Euiwoong Lee, Suprovat Ghoshal · 2022
A µ-biased Max-CSP instance with predicate ψ:{0,1}r → {0,1} is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most µ which satisfies the maximum fraction of constraints. Biased CSPs are versatile and express several well studied problems such as Densest-k-Sub(Hyper)graph and SmallSetExpansion.