Abstract: The projection games problem (also known as LABEL
COVER) is a problem of great significance in the field of hardness
of approximation since almost all NP-hardness of approximation
results known today are derived from the NP-hardness of
approximation of projection games. Hence, it is important to
determine the exact approximation ratio at which projection games
become NP-hard to approximate. The goal of this thesis is to make
progress towards this problem. First and foremost, we present a
polynomial-time approximation algorithm for satisfiable projection
games, which achieves an approximation ratio that is better than
that of the previously best known algorithm. On the hardness of
approximation side, while we do not have any improved NP-hardness
result of approximating LABEL COVER, we show a polynomial
integrality gap for polynomially many rounds of the Lasserre SDP
relaxation for projection games. This result indicates that LABEL
COVER might indeed be hard to approximate to within some polynomial
factor. In addition, we explore special cases of projection games
where the underlying graphs belong to certain families of graphs.
For planar graphs, we present both a subexponential-time exact
algorithm and a polynomial-time approximation scheme (PTAS) for
projection games. We also prove that these algorithms have tight
running times. For dense graphs, we present a subexponential-time
approximation algorithm for LABEL COVER. Moreover, if the graph is
a sufficiently dense random graph, we show that projection games
are easy to approximate to within any polynomial
ratio.
Publication Year: 2015
Publication Date: 2015-01-01
Language: en
Type: dissertation
Access and Citation
Cited By Count: 7
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot