{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:48Z","timestamp":1763467788827,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_74","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"868-875","source":"Crossref","is-referenced-by-count":19,"title":["The Communication Complexity of Approximate Set Packing and Covering"],"prefix":"10.1007","author":[{"given":"Noam","family":"Nisan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"74_CR1","doi-asserted-by":"crossref","unstructured":"R. Aharoni, P. Erods, and N. Linial. Optima of dual integer linear programs. Combinatorica, 8, 1988.","DOI":"10.1007\/BF02122549"},{"issue":"1","key":"74_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137\u2013137, 1999.","journal-title":"Journal of Computer and System Sciences"},{"key":"74_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"V. Chvatal. A greedy heuristic for the set covering problem. Math. Operations Reserach, 4:233\u2013235, 1979.","journal-title":"Math. Operations Reserach"},{"key":"74_CR4","doi-asserted-by":"crossref","unstructured":"Johan Hastad. Clique is hard to approximate to within n1 \u2212 \u03b5. Acta Mathematica, 182, 1999.","DOI":"10.1007\/BF02392825"},{"key":"74_CR5","doi-asserted-by":"crossref","unstructured":"Daniel Lehmann, Liadan Ita O\u2019Callaghan, and Yoav Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. In 1st ACM conference on electronic commerce, 1999.","DOI":"10.1145\/336992.337016"},{"key":"74_CR6","doi-asserted-by":"crossref","unstructured":"L. Lov\u2019asz. The ratio of optimal integral and fractional covers. Discrete Mathematics, 13, 1975.","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"74_CR7","doi-asserted-by":"crossref","unstructured":"Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pages 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"74_CR8","unstructured":"Noam Nisan and Ilya Segal. The communication complexity of efficient allocation problems, 2001. Preliminary version available from http:\/\/www.cs.huji.ac.il\/noam\/mkts.html ."},{"key":"74_CR9","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. On the distributional complexity of disjointness. In ICALP, 1990.","DOI":"10.1007\/BFb0032036"},{"key":"74_CR10","unstructured":"T. Sandholm, S. Suri, A. Gilpin, and Levine D. Cabob: A fast optimal algorithm for combinatorial auctions. In IJCAI, 2001."},{"key":"74_CR11","unstructured":"Rakesh Vohra and Sven de Vries. Combinatorial auctions: A survey, 2000. Availail-abe from http:\/\/www.kellogg.nwu.edu\/faculty\/vohra\/htm\/res.htm ."},{"key":"74_CR12","doi-asserted-by":"crossref","unstructured":"Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In ACM Symposium on Theory of Computing, pages 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"},{"key":"74_CR13","doi-asserted-by":"crossref","unstructured":"Edo Zurel and Noam Nisan. An efficient approximate allocation algorithm for combinatorial auctions. In ACM conference onelectronic commerce, 2001. Available from http:\/\/www.cs.huji.ac.il\/noam\/mkts.html .","DOI":"10.1145\/501158.501172"}],"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-45465-9_74","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:27:31Z","timestamp":1737052051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_74","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}