Constraint Satisfaction

Suppose a CSP instance satisfies the conditions of the Lovasz Local Lemma (LLL). For example, in kSAT where clauses do not repeat variables, we require the maximum degree $D$ is at most $$ D \le \fr...

What is the best polynomial-time approximation ratio achievable for Max Di-Cut? Max Di-Cut is the directed graph version of Max Cut: given a directed graph, find a partition of vertices maximizing ...