{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:02Z","timestamp":1759639082533},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286839"},{"type":"electronic","value":"9783319286846"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_7","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T05:32:03Z","timestamp":1452576723000},"page":"72-83","source":"Crossref","is-referenced-by-count":0,"title":["Buyback Problem with Discrete Concave Valuation Functions"],"prefix":"10.1007","author":[{"given":"Shun","family":"Fukuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akiyoshi","family":"Shioura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Tokuyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-642-22006-7_32","volume-title":"Automata, Languages and Programming","author":"BV Ashwinkumar","year":"2011","unstructured":"Ashwinkumar, B.V.: Buyback problem - approximate matroid intersection with cancellation costs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 379\u2013390. Springer, Heidelberg (2011)"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/978-3-642-10841-9_52","volume-title":"Internet and Network Economics","author":"BV Ashwinkumar","year":"2009","unstructured":"Ashwinkumar, B.V., Kleinberg, R.: Randomized online algorithms for the buyback problem. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 529\u2013536. Springer, Heidelberg (2009)"},{"key":"7_CR3","unstructured":"Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling banner ads: online algorithms with buyback. In: Proceedings of 4th Workshop on Ad Auctions (2008)"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: EC 2009, pp. 61\u201370. ACM, New York (2009)","DOI":"10.1145\/1566374.1566383"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Bing, M., Lehmann, D., Milgrom P.: Presentation and structure of substitutes valuations. In: EC 2004, pp. 238\u2013239. ACM, New York (2004)","DOI":"10.1145\/988772.988812"},{"key":"7_CR6","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 University Press, New York (2007)"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-642-31594-7_13","volume-title":"Automata, Languages, and Programming","author":"N Buchbinder","year":"2012","unstructured":"Buchbinder, N., Naor, J.S., Ravi, R., Singh, M.: Approximation algorithms for online weighted rank function maximization under matroid constraints. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 145\u2013156. Springer, Heidelberg (2012)"},{"key":"7_CR8","first-page":"1202","volume":"2015","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. SODA 2015, 1202\u20131216 (2015)","journal-title":"SODA"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40, 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"7_CR10","first-page":"1265","volume":"2009","author":"F Constantin","year":"2009","unstructured":"Constantin, F., Feldman, J., Muthukrishnan, S., P\u00e1l, M.: An online mechanism for ad slot reservations with cancellations. SODA 2009, 1265\u20131274 (2009)","journal-title":"SODA"},{"key":"7_CR11","volume-title":"Combinatorial Auctions","author":"P Cramton","year":"2006","unstructured":"Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"key":"7_CR12","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. 28, 463\u2013469 (2003)","journal-title":"Math. Oper. Res."},{"key":"7_CR13","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. Theor. 87, 95\u2013124 (1999)","journal-title":"J. Econ. Theor."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s00453-013-9822-z","volume":"70","author":"X Han","year":"2014","unstructured":"Han, X., Kawase, Y., Makino, K.: Online knapsack problem with removal cost. Algorithmica 70, 76\u201391 (2014)","journal-title":"Algorithmica"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-642-38756-2_9","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"X Han","year":"2013","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for removable online knapsack problems. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 60\u201371. Springer, Heidelberg (2013)"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45465-9_26","volume-title":"Automata, Languages and Programming","author":"K Iwama","year":"2002","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 293\u2013305. Springer, Heidelberg (2002)"},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/978-3-642-45030-3_41","volume-title":"Algorithms and Computation","author":"Y Kawase","year":"2013","unstructured":"Kawase, Y., Han, X., Makino, K.: Unit cost buyback problem. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 435\u2013445. Springer, Heidelberg (2013)"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.2307\/1913392","volume":"50","author":"AS Kelso Jr","year":"1982","unstructured":"Kelso Jr., A.S., Crawford, V.P.: Job matching, coalition formation and gross substitutes. Econometrica 50, 1483\u20131504 (1982)","journal-title":"Econometrica"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-642-40450-4_50","volume-title":"Algorithms \u2013 ESA 2013","author":"T Kesselheim","year":"2013","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 589\u2013600. Springer, Heidelberg (2013)"},{"key":"7_CR20","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. 55, 270\u2013296 (2006)","journal-title":"Games Econom. Behav."},{"key":"7_CR21","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. SIAM J. Discrete Math. 9, 545\u2013561 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR22","first-page":"313","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Program. 83, 313\u2013371 (1998)","journal-title":"Math. Program."},{"key":"7_CR23","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)"},{"key":"7_CR24","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, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 219\u2013260. Springer, Berlin (2009)"},{"key":"7_CR25","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. 24, 95\u2013105 (1999)","journal-title":"Math. Oper. Res."},{"key":"7_CR26","unstructured":"Paes Leme, R.: Gross substitutability: An algorithmic survey. preprint (2014)"},{"key":"7_CR27","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/nav.3800090106","volume":"9","author":"L Shapley","year":"1962","unstructured":"Shapley, L.: Complements and substitutes in the optimal assignment problem. Naval Res. Logist. Quart. 9, 45\u201348 (1962)","journal-title":"Naval Res. Logist. Quart."},{"key":"7_CR29","first-page":"1","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. Disc. Math. Alg. Appl. 1, 1\u201323 (2009)","journal-title":"Disc. Math. Alg. Appl."},{"key":"7_CR30","doi-asserted-by":"publisher","first-page":"61","DOI":"10.15807\/jorsj.58.61","volume":"58","author":"A Shioura","year":"2015","unstructured":"Shioura, A., Tamura, A.: Gross substitutes condition and discrete concavity for multi-unit valuations: a survey. J. Oper. Res. Soc. Jpn. 58, 61\u2013103 (2015)","journal-title":"J. Oper. Res. Soc. Jpn."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T05:38:54Z","timestamp":1559367534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}