Improved Parameterized Algorithms for Constraint Satisfaction

Eun Jung Kim, Ryan Williams

For many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment…