Approximation Algorithms for Constraint Satisfaction Problems (thesis)

Report ID: TR-815-08
Author: Makarychev, Yury
Date: 2008-02-00
Pages: 110
Download Formats: |PDF|
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 di erently 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.