{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T01:16:46Z","timestamp":1780363006371,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642208768","type":"print"},{"value":"9783642208775","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_15","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T06:35:17Z","timestamp":1303886117000},"page":"142-153","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions"],"prefix":"10.1007","author":[{"given":"Akiyoshi","family":"Shioura","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shunya","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"15_CR2","volume-title":"Combinatorial Auction","author":"L. Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N.: Algorithmic Game Theory. In: Nisan, N., et al. (eds.) Combinatorial Auction, ch.\u00a011, Cambridge Univ.\u00a0Press, Cambridge (2007)"},{"key":"15_CR3","volume-title":"Combinatorial Auctions","author":"P. Cramton","year":"2006","unstructured":"Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1137\/S0097539791278376","volume":"25","author":"J. Cheriyan","year":"1996","unstructured":"Cheriyan, J., Hagerup, T., Mehlhorn, K.: An o(n)-time maximum-flow algorithm. SIAM J.\u00a0Comput.\u00a025, 1144\u20131170 (1996)","journal-title":"SIAM J.\u00a0Comput."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10479-008-0335-0","volume":"163","author":"Y. Chevaleyre","year":"2008","unstructured":"Chevaleyre, Y., Endriss, U., Estivie, S., Maudet, N.: Multiagent resource allocation in k-additive domains: preference representation and complexity. Annals Oper. Res.\u00a0163, 49\u201362 (2008)","journal-title":"Annals Oper. Res."},{"key":"15_CR6","unstructured":"Conitzer, V., Sandholm, T., Santi, P.: Combinatorial auctions with k-wise dependent valuations. In: Proc. AAAI 2005, pp. 248\u2013254 (2005)"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J.\u00a0Comput.\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J.\u00a0Comput."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM\u00a034, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"15_CR9","volume-title":"Submodular Function and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Function and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1287\/moor.28.3.463.16393","volume":"28","author":"S. Fujishige","year":"2003","unstructured":"Fujishige, S., Yang, Z.: A note on Kelso and Crawford\u2019s gross substitutes condition. Math. Oper. Res.\u00a028, 463\u2013469 (2003)","journal-title":"Math. Oper. Res."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1984)","journal-title":"Combinatorica"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1006\/jeth.1999.2531","volume":"87","author":"F. Gul","year":"1999","unstructured":"Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. J.\u00a0Econ.\u00a0Theory\u00a087, 95\u2013124 (1999)","journal-title":"J.\u00a0Econ.\u00a0Theory"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"P.L. Hammer","year":"1965","unstructured":"Hammer, P.L.: Some network flow problems solved with pseudo-Boolean programming. Oper. Res.\u00a013, 388\u2013399 (1965)","journal-title":"Oper. Res."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/BF03167590","volume":"21","author":"H. Hirai","year":"2004","unstructured":"Hirai, H., Murota, K.: M-convex functions and tree metrics. Japan J.\u00a0Indust. Appl. Math.\u00a021, 391\u2013403 (2004)","journal-title":"Japan J.\u00a0Indust. Appl. Math."},{"key":"15_CR15","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 Econom. Behav.\u00a047, 104\u2013123 (2004)","journal-title":"Games Econom. Behav."},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.2307\/1913392","volume":"50","author":"A.S. Kelso","year":"1982","unstructured":"Kelso, A.S., Crawford, V.P.: Job matching, coalition formation and gross substitutes. Econometrica\u00a050, 1483\u20131504 (1982)","journal-title":"Econometrica"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable CSPs? In: Proc. FOCS, pp. 146\u2013154 (2004)","DOI":"10.1109\/FOCS.2004.49"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-007-9105-7","volume":"52","author":"S. Khot","year":"2008","unstructured":"Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica\u00a052, 3\u201318 (2008)","journal-title":"Algorithmica"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J. Kleinberg","year":"2002","unstructured":"Kleinberg, J., Tardos, \u00c9.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. J. ACM\u00a049, 616\u2013639 (2002)","journal-title":"J. ACM"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V. Kolmogorov","year":"2004","unstructured":"Kolmogorov, V.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell.\u00a026, 147\u2013159 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/11830924_18","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Langberg","year":"2006","unstructured":"Langberg, M., Rabani, Y., Swamy, C.: Approximation algorithms for graph homomorphism problems. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 176\u2013187. Springer, Heidelberg (2006)"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B. Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav.\u00a055, 270\u2013296 (2006)","journal-title":"Games Econom. Behav."},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O\u2019Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: Proc. EC 1999, pp. 96\u2013102 (1999)","DOI":"10.1145\/336992.337016"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-47867-1_6","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Lewin","year":"2002","unstructured":"Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 67\u201382. Springer, Heidelberg (2002)"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Mirrokni, V., Schapira, M., Vondr\u00e1k, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proc. EC 2008, pp. 70\u201377 (2008)","DOI":"10.1145\/1386790.1386805"},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/s00199-001-0248-5","volume":"20","author":"H. Reijniese","year":"2002","unstructured":"Reijniese, H., van Gellekom, A., Potters, J.A.M.: Verifying gross substitutability. Econom. Theory\u00a020, 767\u2013776 (2002)","journal-title":"Econom. Theory"},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0004-3702(01)00159-X","volume":"135","author":"T. Sandholm","year":"2002","unstructured":"Sandholm, T.: Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence\u00a0135, 1\u201354 (2002)","journal-title":"Artificial Intelligence"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proc. STOC 2008, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T08:26:49Z","timestamp":1741163209000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}