On Regularity of Max-CSPs and Min-CSPs

Aleksa Stankovic

We study approximability of regular constraint satisfaction problems, i.e., CSPs where each variable in an instance has the same number of occurrences. In particular, we show that…