The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
We suggest the research agenda of establishing new hardness of approximation results based on the “projection games conjecture”, i.e., an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We pursue this line of research by establishing a tig...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90484 https://orcid.org/0000-0002-5157-8086 |