{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:17Z","timestamp":1781077817517,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325113","type":"print"},{"value":"9783642325120","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_24","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"276-287","source":"Crossref","is-referenced-by-count":19,"title":["The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover"],"prefix":"10.1007","author":[{"given":"Dana","family":"Moshkovitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"24_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms\u00a02, 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"24_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"24_CR4","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proc. 25th ACM Symp. on Theory of Computing, pp. 294\u2013304 (1993)","DOI":"10.1145\/167088.167174"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-04128-0_3","volume-title":"Algorithms - ESA 2009","author":"M. Charikar","year":"2009","unstructured":"Charikar, M., Hajiaghayi, M., Karloff, H.: Improved Approximation Algorithms for Label Cover Problems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 23\u201334. Springer, Heidelberg (2009)"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"16","key":"24_CR8","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M. Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inf. Process. Lett.\u00a0109(16), 957\u2013961 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"24_CR9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00037-011-0014-4","volume":"20","author":"I. Dinur","year":"2011","unstructured":"Dinur, I., Fischer, E., Kindler, G., Raz, R., Safra, S.: PCP characterizations of NP: Toward a polynomially-small error-probability. Computational Complexity\u00a020(3), 413\u2013504 (2011)","journal-title":"Computational Complexity"},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"issue":"4","key":"24_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: Proc. 42nd IEEE Symp. on Foundations of Computer Science, pp. 600\u2013609 (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34th ACM Symp. on Theory of Computing, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"5","key":"24_CR15","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1145\/1089023.1089027","volume":"52","author":"S. Khot","year":"2005","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM\u00a052(5), 789\u2013808 (2005)","journal-title":"Journal of the ACM"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. In: Proc. 25th ACM Symp. on Theory of Computing (1993)","DOI":"10.1145\/167088.167172"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two query PCP with sub-constant error. Journal of the ACM\u00a057(5) (2010)","DOI":"10.1145\/1754399.1754402"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proc. 36th IEEE Symp. on Foundations of Computer Science, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM Journal on Computing\u00a027, 763\u2013803 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. on Theory of Computing, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Slav\u00edk, P.: A tight analysis of the greedy algorithm for set cover. In: Proc. 28th ACM Symp. on Theory of Computing, pp. 435\u2013441 (1996)","DOI":"10.1145\/237814.237991"},{"issue":"2","key":"24_CR22","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximations guarantees for packing and covering integer programs. SIAM Journal on Computing\u00a029(2), 648\u2013670 (1999)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:25:02Z","timestamp":1743823502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}