Improved Approximation Algorithms for Projection Games

Improved Approximation Algorithms for Projection Games

Show other versions (1)

The projection games (aka Label-Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label-Cover. In this paper we design several approximation algorithms for projection games: 1. A p...

Full description

Bibliographic Details
Main Authors: Manurangsi, Pasin, Moshkovitz Aaronson, Dana Hadar
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Springer-Verlag 2014
Online Access:http://hdl.handle.net/1721.1/90487
https://orcid.org/0000-0002-5157-8086

Internet

http://hdl.handle.net/1721.1/90487
https://orcid.org/0000-0002-5157-8086

Similar Items