Approximation Algorithms for Constraint Satisfaction Problems (thesis)

Abstract:

Constraint satisfaction problems (CSP) are very basic and natural combinatorial
optimization problems. Given a set of variables and constraints on them, our goal
is to satisfy as many constraints as possible.

In this dissertation, we study two constraint satisfaction problems, the Unique
Games Problem and MAX 2CSP Problem. Both problems behave very dierently
depending on what fraction of all constraints (as a function of other parameters) is
satisfiable. Thus we design different algorithms for different ranges of parameters.

In the first part of the thesis, we study approximation algorithms for Unique
Games. Our algorithms satisfy (roughly)
k^-epsilon/(2-epsilon); 1-O (sqrt (epsilon*log n)); and 1-O (epsilon*sqrt (log n * log k))
fraction of all constraints if a 1 - epsilon fraction of all constraints is satisfiable (where
n is the number of variables, k is the domain size). The first two algorithms are
near optimal assuming the Unique Games Conjecture. Our algorithms have better
approximation guarantees than the previously best known algorithms in all ranges
of parameters.

In the second part of the thesis, we present approximation algorithms for MAX
2CSP that satisfy 1-O(sqrt epsilon) and 1-O (epsilon*sqrt log n) fraction of all constraints if a 1-epsilon fraction of all constraints is satifiable. Our first algorithm is near optimal assuming
the Unique Games Conjecture.