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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Manurangsi, Pasin

Advisor dc:contributor.advisor

• Dana Moshkovitz.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/100635

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/100635