{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:14:30Z","timestamp":1781259270067,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s00453-007-9105-7","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T15:42:43Z","timestamp":1192203763000},"page":"3-18","source":"Crossref","is-referenced-by-count":29,"title":["Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions"],"prefix":"10.1007","volume":"52","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9105_CR1","doi-asserted-by":"crossref","unstructured":"Andelman, N., Mansour, Y.: Auctions with budget constraints. In: Scandinavian Workshop on Algorithm Theory, pp.\u00a026\u201338 (2004)","DOI":"10.1007\/978-3-540-27810-8_4"},{"key":"9105_CR2","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., Tardos, E.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0205\u2013214 (2003)"},{"issue":"3","key":"9105_CR3","doi-asserted-by":"crossref","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 intractability of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"9105_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: Theoretical Aspects of Rationality and Knowledge, pp.\u00a072\u201387 (2003)","DOI":"10.1145\/846241.846250"},{"key":"9105_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, pp.\u00a029\u201343 (2005)","DOI":"10.1145\/1064009.1064013"},{"key":"9105_CR6","volume-title":"Combinatorial Auctions","year":"2006","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"key":"9105_CR7","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: ACM Symposium on Theory of Computing, pp.\u00a0610\u2013618 (2005)","DOI":"10.1145\/1060590.1060681"},{"key":"9105_CR8","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: ACM Symposium on Theory of Computing, pp.\u00a051\u201360 (2006)","DOI":"10.1145\/1132516.1132607"},{"key":"9105_CR9","unstructured":"Dobzinski, S., Schapira, M.: Private communication (2006)"},{"key":"9105_CR10","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a01064\u20131073 (2006)","DOI":"10.1145\/1109557.1109675"},{"issue":"4","key":"9105_CR11","doi-asserted-by":"crossref","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. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9105_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. In: ACM Symposium on Theory of Computing, pp.\u00a041\u201350 (2006)","DOI":"10.1145\/1132516.1132523"},{"issue":"1","key":"9105_CR13","doi-asserted-by":"crossref","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 J. Comput. 32(1), 172\u2013195 (2002)","journal-title":"SIAM J. Comput."},{"key":"9105_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57, 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9105_CR15","unstructured":"Feige, U., Vondrak, J.: The allocation problem with submodular utility functions. In: IEEE Symposium on Foundations of Computer Science (2006)"},{"key":"9105_CR16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jeth.1999.2580","volume":"87","author":"F. Gul","year":"2000","unstructured":"Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. J. Econ. Theory 87, 66\u201395 (2000)","journal-title":"J. Econ. Theory"},{"key":"9105_CR17","doi-asserted-by":"crossref","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 Econ. Behav. 47, 104\u2013123 (2004)","journal-title":"Games Econ. Behav."},{"key":"9105_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. In: Workshop on Internet and Network Economics, pp.\u00a092\u2013101 (2005)","DOI":"10.1007\/11600930_10"},{"key":"9105_CR19","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: ACM Conference on Electronic Commerce, pp.\u00a018\u201328 (2001)","DOI":"10.1145\/501158.501161"},{"key":"9105_CR20","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, pp.\u00a096\u2013102 (1999)","DOI":"10.1145\/336992.337016"},{"issue":"5","key":"9105_CR21","doi-asserted-by":"crossref","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. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"9105_CR22","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jet.2004.10.007","volume":"129","author":"N. Nisan","year":"2004","unstructured":"Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting lindahl prices. J. Econ. Theory 129(1), 192\u2013224 (2004)","journal-title":"J. Econ. Theory"},{"key":"9105_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: Gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"issue":"3","key":"9105_CR24","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"9105_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0004-3702(01)00159-X","volume":"135","author":"T. Sandholm","year":"2002","unstructured":"Sandholm, T.: An algorithm for optimal winner determination in combinatorial auctions. Artif. Intell. 135, 1\u201354 (2002)","journal-title":"Artif. Intell."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9105-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9105-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9105-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9105-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["9105"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9105-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}