Improved Approximation Algorithms for Projection Games
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...
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 |
Similar Items
-
Improved Approximation Algorithms for Projection Games
by: Manurangsi, Pasin, et al.
Published: (2017) -
The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014) -
On approximating projection games
by: Manurangsi, Pasin
Published: (2016) -
NP-Hardness of Approximately Solving Linear Equations Over Reals
by: Khot, Subhash, et al.
Published: (2011) -
Parallel Repetition From Fortification
by: Moshkovitz Aaronson, Dana Hadar
Published: (2014)