{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T22:59:20Z","timestamp":1762210760766},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_47","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"563-575","source":"Crossref","is-referenced-by-count":16,"title":["Changing Bases: Multistage Optimization for Matroids and Matchings"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[]},{"given":"Udi","family":"Wieder","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"47_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-642-16108-7_23","volume-title":"Algorithmic Learning Theory","author":"J. Abernethy","year":"2010","unstructured":"Abernethy, J., Bartlett, P.L., Buchbinder, N., Stanton, I.: A regularization approach to metrical task systems. In: Hutter, M., Stephan, F., Vovk, V., Zeugmann, T. (eds.) Algorithmic Learning Theory. LNCS, vol.\u00a06331, pp. 270\u2013284. Springer, Heidelberg (2010)"},{"issue":"4","key":"47_CR2","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/PL00009263","volume":"23","author":"M. Andrews","year":"1999","unstructured":"Andrews, M., Goemans, M.X., Zhang, L.: Improved bounds for on-line load balancing. Algorithmica\u00a023(4), 278\u2013301 (1999)","journal-title":"Algorithmica"},{"key":"47_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-540-72792-7_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"B.M. Anthony","year":"2007","unstructured":"Anthony, B.M., Gupta, A.: Infrastructure leasing problems. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 424\u2013438. Springer, Heidelberg (2007)"},{"key":"47_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-642-14165-2_25","volume-title":"Automata, Languages and Programming","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Buchbinder, N., Naor, J(S.): Metrical task systems and the k-server problem on hSTs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 287\u2013298. Springer, Heidelberg (2010)"},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.S.: Randomized competitive algorithms for generalized caching. In: STOC 2008, pp. 235\u2013244 (2008)","DOI":"10.1145\/1374376.1374412"},{"issue":"4","key":"47_CR6","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM\u00a039(4), 745\u2013763 (1992)","journal-title":"J. ACM"},{"key":"47_CR7","unstructured":"Buchbinder, N., Chen, S., Naor, J., Shamir, O.: Unified algorithms for online learning and competitive analysis. JMLR 23, 5.1\u20135.18 (2012)"},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Chen, S., Naor, J.S.: Competitive analysis via regularization. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 436\u2013444 (2014)","DOI":"10.1137\/1.9781611973402.32"},{"issue":"2","key":"47_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Math. Oper. Res.\u00a034(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract), pp. 182\u2013196 (2007)","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction, learning, and games. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511546921"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC, pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"47_CR13","unstructured":"Cohen, E., Cormode, G., Duffield, N.G., Lund, C.: On the tradeoff between stability and fit. CoRR abs\/1302.2137 (2013)"},{"key":"47_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-642-23719-5_48","volume-title":"Algorithms \u2013 ESA 2011","author":"L. Epstein","year":"2011","unstructured":"Epstein, L., Levin, A.: Robust algorithms for preemptive scheduling. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 567\u2013578. Springer, Heidelberg (2011)"},{"key":"47_CR15","doi-asserted-by":"crossref","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive steiner tree online. In: STOC, pp. 525\u2013534 (2013)","DOI":"10.1145\/2488608.2488674"},{"key":"47_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-642-31594-7_37","volume-title":"Automata, Languages, and Programming","author":"A. Gupta","year":"2012","unstructured":"Gupta, A., Nagarajan, V.: Approximating sparse covering integer programs online. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 436\u2013448. Springer, Heidelberg (2012)"},{"key":"47_CR17","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Wieder, U.: Changing bases: Multistage optimization for matroids and matchings. In: arXiv:1404.3768 (2014)","DOI":"10.1007\/978-3-662-43948-7_47"},{"key":"47_CR18","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discrete Math. 4(3), 369\u2013384 (1991)"},{"key":"47_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/978-3-642-31594-7_58","volume-title":"Automata, Languages, and Programming","author":"N. Megow","year":"2012","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 689\u2013700. Springer, Heidelberg (2012)"},{"key":"47_CR20","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: The parking permit problem. In: FOCS. pp. 274\u2013284 (2005)","DOI":"10.1109\/SFCS.2005.72"},{"key":"47_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-68891-4_21","volume-title":"Integer Programming and Combinatorial Optimization","author":"C. Nagarajan","year":"2008","unstructured":"Nagarajan, C., Williamson, D.P.: Offline and online facility leasing. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 303\u2013315. Springer, Heidelberg (2008)"},{"key":"47_CR22","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)"},{"key":"47_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/978-3-642-29344-3_52","volume-title":"LATIN 2012: Theoretical Informatics","author":"H. Shachnai","year":"2012","unstructured":"Shachnai, H., Tamir, G., Tamir, T.: A theory and algorithms for combinatorial reoptimization. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 618\u2013630. Springer, Heidelberg (2012)"},{"issue":"4","key":"47_CR24","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T12:41:20Z","timestamp":1565527280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}