{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T19:08:42Z","timestamp":1751483322784},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309000"},{"type":"electronic","value":"9783540322931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11600930_10","type":"book-chapter","created":{"date-parts":[[2005,11,24]],"date-time":"2005-11-24T14:48:12Z","timestamp":1132843692000},"page":"92-101","source":"Crossref","is-referenced-by-count":24,"title":["Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-540-27810-8_4","volume-title":"Algorithm Theory - SWAT 2004","author":"N. Andelman","year":"2004","unstructured":"Andelman, N., Mansour, Y.: Auctions with budget constraints. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 26\u201338. Springer, Heidelberg (2004)"},{"key":"10_CR2","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., Tardos, E.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: SODA, pp. 205\u2013214 (2003)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: FOCS, pp. 14\u201323 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: TARK, pp. 72\u201387 (2003)","DOI":"10.1145\/846241.846250"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Blumrosen, L., Nisan, N.: On the computational power of ascending auctions 1: Demand queries. In: ACM Conference on Electronic Commerce (2005)","DOI":"10.1145\/1064009.1064013"},{"volume-title":"Combinatorial Auctions","year":"2005","key":"10_CR6","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2005) (forthcoming)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC (2005)","DOI":"10.1145\/1060590.1060681"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. Working paper (2005)","DOI":"10.1145\/1060590.1060681"},{"issue":"4","key":"10_CR9","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 lnn for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U. Feige","year":"2002","unstructured":"Feige, U., Halldorsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM Journal of Computing\u00a032(1), 172\u2013195 (2002)","journal-title":"SIAM Journal of Computing"},{"key":"10_CR11","first-page":"187","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. JCSS\u00a057, 187\u2013199 (1998)","journal-title":"JCSS"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/S0899-8256(03)00184-2","volume":"47","author":"R. Holzman","year":"2004","unstructured":"Holzman, R., Kfir-Dahav, N., Monderer, D., Tennenholtz, M.: Bundling equilibrium in combinatorial auctions. Games and Economic Behavior\u00a047, 104\u2013123 (2004)","journal-title":"Games and Economic Behavior"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: ACM Conference on Electronic Commerce (2001)","DOI":"10.1145\/501158.501161"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O\u2019Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: ACM Conference on Electronic Commerce (1999)","DOI":"10.1145\/336992.337016"},{"issue":"5","key":"10_CR15","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"Journal of the ACM"},{"key":"10_CR16","unstructured":"Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting lindahl prices. To appear in Journal of Economic Theory (2004), preliminary version: http:\/\/www.cs.huji.ac.il\/~noam\/mkts.html"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"10_CR18","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 of Computing\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"10_CR19","unstructured":"Sandholm, T.: An algorithm for optimal winner determination in combinatorial auctions. In: IJCAI (1999)"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11600930_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:01:00Z","timestamp":1619506860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11600930_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309000","9783540322931"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11600930_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}