| 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 differently 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-3/2-3 ,1-O3log n,and 1-O3lognlog k fraction of all constraints if a 1-&egr; 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( 3 ) and 1-O( 3logn ) fraction of all constraints if a 1-&egr; fraction of all constraints is satisfiable. Our first algorithm is near optimal assuming the Unique Games Conjecture. |
