{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:39Z","timestamp":1725603639947},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"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-23719-5_1","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"1-12","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints"],"prefix":"10.1007","author":[{"given":"Akiyoshi","family":"Shioura","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Ausubel, L.M., Milgrom, P.: Ascending auctions with package bidding. Front. Theor. Econ.\u00a01, Article 1 (2002)","DOI":"10.2202\/1534-5955.1019"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Berger, A., Bonifaci, V., Grandoni, F., Sch\u00e4fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math. Programming (2009) (to appear)","DOI":"10.1007\/s10107-009-0307-4"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Bing, M., Lehmann, D., Milgrom, P.: Presentation and structure of substitutes valuations. In: Proc.\u00a0EC 2004, pp. 238\u2013239 (2004)","DOI":"10.1145\/988772.988812"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1017\/CBO9780511800481.013","volume-title":"Algorithmic Game Theory","author":"L. Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N.: Combinatorial auction. In: Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V. (eds.) Algorithmic Game Theory, pp. 267\u2013299. Cambridge Univ. Press, Cambridge (2007)"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (Extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"key":"1_CR6","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. (to appear)"},{"key":"1_CR7","volume-title":"Combinatorial Auctions","author":"P. Cramton","year":"2006","unstructured":"Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: On submodular function minimization. Combinatorica\u00a05, 185\u2013192 (1985)","journal-title":"Combinatorica"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"A.W.M. Dress","year":"1992","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math.\u00a093, 214\u2013250 (1992)","journal-title":"Adv. Math."},{"key":"1_CR10","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 ln n for approximating set cover. J. ACM\u00a045, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/070680977","volume":"39","author":"U. Feige","year":"2009","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput.\u00a039, 122\u2013142 (2009)","journal-title":"SIAM J. Comput."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. In: Proc. FOCS 2007, pp. 461\u2013471 (2007)","DOI":"10.1109\/FOCS.2007.4389516"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A. Frank","year":"1988","unstructured":"Frank, A., Tardos, \u00c9.: Generalized polymatroids and submodular flows. Math. Programming\u00a042, 489\u2013563 (1988)","journal-title":"Math. Programming"},{"key":"1_CR14","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"1_CR15","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":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-642-15775-2_46","volume-title":"Algorithms \u2013 ESA 2010","author":"F. Grandoni","year":"2010","unstructured":"Grandoni, F., Zenklusen, R.: Approximation schemes for multi-budgeted independence systems. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 536\u2013548. Springer, Heidelberg (2010)"},{"key":"1_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd edn. Springer, Heidelberg (1993)","edition":"2"},{"key":"1_CR18","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. Econ. Theory\u00a087, 95\u2013124 (1999)","journal-title":"J. Econ. Theory"},{"key":"1_CR19","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":"1_CR20","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proc. SODA 2009, pp. 545\u2013554 (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J. Lee","year":"2010","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math.\u00a023, 2053\u20132078 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1_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":"1_CR23","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res.\u00a021, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Math. Oper. Res.\u00a04, 414\u2013424 (1979)","journal-title":"Math. Oper. Res."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/aima.1996.0084","volume":"124","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Convexity and Steinitz\u2019s exchange property. Adv. Math.\u00a0124, 272\u2013311 (1996)","journal-title":"Adv. Math."},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, I: optimality criteria, II: algorithms. SIAM J. Discrete Math.\u00a09, 545\u2013561, 562\u2013576 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR27","first-page":"313","volume":"83","author":"K. Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Programming\u00a083, 313\u2013371 (1998)","journal-title":"Math. Programming"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)","DOI":"10.1137\/1.9780898718508"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-76796-1_11","volume-title":"Research Trends in Combinatorial Optimization","author":"K. Murota","year":"2009","unstructured":"Murota, K.: Recent developments in discrete convex analysis. In: Cook, W.J., Lov\u00e1sz, J., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 219\u2013260. Springer, Heidelberg (2009)"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1287\/moor.24.1.95","volume":"24","author":"K. Murota","year":"1999","unstructured":"Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res.\u00a024, 95\u2013105 (1999)","journal-title":"Math. Oper. Res."},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1006\/aama.2000.0702","volume":"25","author":"K. Murota","year":"2000","unstructured":"Murota, K., Shioura, A.: Extension of M-convexity and L-convexity to polyhedral convex functions. Adv. in Appl. Math.\u00a025, 352\u2013427 (2000)","journal-title":"Adv. in Appl. Math."},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF03167422","volume":"20","author":"K. Murota","year":"2003","unstructured":"Murota, K., Tamura, A.: Application of M-convex submodular flow problem to mathematical economics. Japan J. Indust. Appl. Math.\u00a020, 257\u2013277 (2003)","journal-title":"Japan J. Indust. Appl. Math."},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S0166-218X(02)00469-9","volume":"131","author":"K. Murota","year":"2003","unstructured":"Murota, K., Tamura, A.: New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities. Discrete Appl. Math.\u00a0131, 495\u2013512 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-61422-2_121","volume-title":"Algorithm Theory - SWAT \u201996","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 66\u201375. Springer, Heidelberg (1996)"},{"key":"1_CR35","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"R.T. Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0166-218X(97)00140-6","volume":"84","author":"A. Shioura","year":"1998","unstructured":"Shioura, A.: Minimization of an M-convex function. Discrete Appl. Math.\u00a084, 215\u2013220 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S1793830909000063","volume":"1","author":"A. Shioura","year":"2009","unstructured":"Shioura, A.: On the pipage rounding algorithm for submodular function maximization: a view from discrete convex analysis. Discrete Math. Algorithms Appl.\u00a01, 1\u201323 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"1_CR38","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett.\u00a032, 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res.\u00a07, 410\u2013425 (1982)","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:07:47Z","timestamp":1560528467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}