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 |
| _version_ | 1811070093208059904 |
|---|---|
| author | Moshkovitz Aaronson, Dana Hadar |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Moshkovitz Aaronson, Dana Hadar |
| author_sort | Moshkovitz Aaronson, Dana Hadar |
| collection | MIT |
| description | 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 tight NP-hardness result for the Set-Cover problem. Specifically, we show that under the projection games conjecture (in fact, under a quantitative version of the conjecture that is only slightly beyond the reach of current techniques), it is NP-hard to approximate Set-Cover on instances of size N to within (1 − α)ln N for arbitrarily small α > 0. Our reduction establishes a tight trade-off between the approximation accuracy α and the time required for the approximation 2[superscript NΩ(α)], assuming Sat requires exponential time.
The reduction is obtained by modifying Feige’s reduction. The latter only provides a lower bound of 2[superscript NΩ(α/loglogN)] on the time required for (1 − α)ln N-approximating Set-Cover assuming Sat requires exponential time (note that N[superscript 1/loglogN] = N[superscript o(1)]). The modification uses a combinatorial construction of a bipartite graph in which any coloring of the first side that does not use a color for more than a small fraction of the vertices, makes most vertices on the other side have their neighbors all colored in different colors. |
| first_indexed | 2024-09-23T08:24:08Z |
| format | Article |
| id | mit-1721.1/90484 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:24:08Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/904842022-09-30T09:15:30Z The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover Moshkovitz Aaronson, Dana Hadar Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Moshkovitz Aaronson, Dana Hadar 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 tight NP-hardness result for the Set-Cover problem. Specifically, we show that under the projection games conjecture (in fact, under a quantitative version of the conjecture that is only slightly beyond the reach of current techniques), it is NP-hard to approximate Set-Cover on instances of size N to within (1 − α)ln N for arbitrarily small α > 0. Our reduction establishes a tight trade-off between the approximation accuracy α and the time required for the approximation 2[superscript NΩ(α)], assuming Sat requires exponential time. The reduction is obtained by modifying Feige’s reduction. The latter only provides a lower bound of 2[superscript NΩ(α/loglogN)] on the time required for (1 − α)ln N-approximating Set-Cover assuming Sat requires exponential time (note that N[superscript 1/loglogN] = N[superscript o(1)]). The modification uses a combinatorial construction of a bipartite graph in which any coloring of the first side that does not use a color for more than a small fraction of the vertices, makes most vertices on the other side have their neighbors all colored in different colors. 2014-09-30T16:56:24Z 2014-09-30T16:56:24Z 2012 Article http://purl.org/eprint/type/JournalArticle 978-3-642-32511-3 978-3-642-32512-0 0302-9743 1611-3349 http://hdl.handle.net/1721.1/90484 Moshkovitz, Dana. “The Projection Games Conjecture and the NP-Hardness of Ln n-Approximating Set-Cover.” Lecture Notes in Computer Science (2012): 276–287. https://orcid.org/0000-0002-5157-8086 en_US http://dx.doi.org/10.1007/978-3-642-32512-0_24 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Moshkovitz Aaronson, Dana Hadar The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title | The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title_full | The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title_fullStr | The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title_full_unstemmed | The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title_short | The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover |
| title_sort | projection games conjecture and the np hardness of ln n approximating set cover |
| url | http://hdl.handle.net/1721.1/90484 https://orcid.org/0000-0002-5157-8086 |
| work_keys_str_mv | AT moshkovitzaaronsondanahadar theprojectiongamesconjectureandthenphardnessoflnnapproximatingsetcover AT moshkovitzaaronsondanahadar projectiongamesconjectureandthenphardnessoflnnapproximatingsetcover |