{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:15:18Z","timestamp":1773656118351,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540677154","type":"print"},{"value":"9783540450221","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_53","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"624-635","source":"Crossref","is-referenced-by-count":38,"title":["Hardness of Set Cover with Intersection 1"],"prefix":"10.1007","author":[{"given":"V. S. Anil","family":"Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunil","family":"Arya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Ramesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"53_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, O. Goldreich, J. Hastad, R. Perralta. Simple Constructions of Almost k-Wise Independent Random Variables. Random Structures and Algorithms, 3, 1992.","DOI":"10.1002\/rsa.3240030308"},{"key":"53_CR2","doi-asserted-by":"crossref","unstructured":"V.S. Anil Kumar and H. Ramesh. Covering Rectilinear Polygons with Axis-Parallel Rectangles. Proceedings of 31st ACM-SIAM Symposium in Theory of Computing, 1999.","DOI":"10.1145\/301250.301369"},{"key":"53_CR3","unstructured":"S. Arora, C. Lund. Hardness of Approximation. In Approximation Algorithms for NP-Hard Problems, Ed. D. Hochbaum, PWS Publishers, 1995, pp. 399\u2013446."},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. Proof Verification and Intractability of Approximation Problems. Proceedings of 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 13\u201322.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"53_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora, M. Sudan. Improved Low Degree Testing and Applications. Proceedings of the ACM Symposium on Theory of Computing, 1997, pp. 485\u2013495.","DOI":"10.1145\/258533.258642"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"J. Beck. An Algorithmic Approach to the Lovasz Local Lemma I, Random Structures and Algorithms, 2, 1991, pp. 343\u2013365.","journal-title":"Random Structures and Algorithms"},{"key":"53_CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russell. Efficient Probabilistically Checkable Proofs and Applications to Approximation, Proceedings of 25th ACM Symposium on Theory of Computing, 1993, pp. 294\u2013303.","DOI":"10.1145\/167088.167174"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"H. Br\u00f6nnimann, M. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Discrete Comput. Geom., 14, 1995, pp. 263\u2013279.","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"53_CR9","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1109\/32.6142","volume":"14","author":"Y. Cheng","year":"1988","unstructured":"Y. Cheng, S.S. Iyengar and R.L. Kashyap. A New Method for Image compression using Irreducible Covers of Maximal Rectangles. IEEE Transactions on Software Engineering, Vol. 14,5, 1988, pp. 651\u2013658.","journal-title":"IEEE Transactions on Software Engineering"},{"issue":"4","key":"53_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige. A threshold of ln n for Approximating Set Cover. Journal of the ACM, 45,4, 1998, pp. 634\u2013652.","journal-title":"Journal of the ACM"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(91)90011-K","volume":"30","author":"R. Hassin","year":"1991","unstructured":"R. Hassin and N. Megiddo. Approximation Algorithms for Hitting Objects with Straight Lines. Discrete Applied Mathematics, 30, 1991, pp. 29\u201342.","journal-title":"Discrete Applied Mathematics"},{"key":"53_CR12","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computing and Systems Sciences, 9, 1974, pp. 256\u2013278.","journal-title":"Journal of Computing and Systems Sciences"},{"key":"53_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of 6th Foundations of Software Tech. and Theoretical Comp. Sc.","author":"C. Levcopoulos","year":"1987","unstructured":"C. Levcopoulos. Improved Bounds for Covering General Polygons by Rectangles. Proceedings of 6th Foundations of Software Tech. and Theoretical Comp. Sc. LNCS 287, 1987."},{"key":"53_CR14","unstructured":"N. Linial, M. Luby, M. Saks, D. Zuckerman. Hitting Sets for Combinatorial Rectangles. Proceedings of 25 ACM Symposium on Theory of Computing, 1993, pp. 286\u2013293."},{"key":"53_CR15","doi-asserted-by":"crossref","unstructured":"C. Lund, M. Yannakakis. On the Hardness of Approximating Minimization Problems. Proceedings of 25th ACM Symposium on Theory of Computing, 1993, pp. 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"53_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"N. Megiddo and A. Tamir, On the complexity of locating linear facilities in the plane, Oper. Res. Let, 1, 1982, pp. 194\u2013197.","journal-title":"Oper. Res. Let"},{"key":"53_CR17","doi-asserted-by":"crossref","unstructured":"M. Naor, L. Schulman, A. Srinivasan. Splitters and Near-Optimal Derandomization. Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, 1995, pp. 182\u2013191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"53_CR18","doi-asserted-by":"crossref","unstructured":"R. Raz. A Parallel Repetition Theorem. Proceedings of the 27th ACM Symposium on Theory of Computing, 1995, pp. 447\u2013456.","DOI":"10.1145\/225058.225181"},{"key":"53_CR19","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra. A Sub-Constant Error-Probability Low-Degree test and a Sub-Constant Error-Probability PCP Characterization of NP. Proceedings of the ACM Symposium on Theory of Computing, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"53_CR20","unstructured":"Madhu Sudan. Personal communication."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T11:25:09Z","timestamp":1556969109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_53","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}