On approximating projection games

[摘要] 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.

[发布机构] Massachusetts Institute of Technology