{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:08Z","timestamp":1740109268761,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T00:00:00Z","timestamp":1578009600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T00:00:00Z","timestamp":1578009600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["2233\/19"],"award-info":[{"award-number":["2233\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2018352"],"award-info":[{"award-number":["2018352"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1357\/16","1337\/16"],"award-info":[{"award-number":["1357\/16","1337\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Taub Foundations"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-019-01459-z","type":"journal-article","created":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T08:03:02Z","timestamp":1578038582000},"page":"149-169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Online submodular maximization: beating 1\/2 made simple"],"prefix":"10.1007","volume":"183","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7014-8954","authenticated-orcid":false,"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1739-0872","authenticated-orcid":false,"given":"Yuval","family":"Filmus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1230-4821","authenticated-orcid":false,"given":"Mohit","family":"Garg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,3]]},"reference":[{"key":"1459_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: SODA, pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"1459_CR2","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: EC, pp. 18\u201335 (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"1459_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA, pp. 1497\u20131514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"1459_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Filmus, Y., Garg, M.: Online submodular maximization: beating 1\/2 made simple. In: IPCO, pp. 101\u2013114 (2019)","DOI":"10.1007\/978-3-030-17953-3_8"},{"key":"1459_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Garg, M.: Deterministic $$({1}\/{2}+\\varepsilon )$$-approximation for submodular maximization over a matroid. In: SODA, pp. 241\u2013254 (2019)","DOI":"10.1137\/1.9781611975482.16"},{"issue":"2","key":"1459_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Comparing apples and oranges: query trade-off in submodular maximization. Math. Oper. Res. 42(2), 308\u2013329 (2017)","journal-title":"Math. Oper. Res."},{"key":"1459_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Jain, K., Naor, J.: Online primal\u2013dual algorithms for maximizing ad-auctions revenue. In: ESA, pp. 253\u2013264 (2007)","DOI":"10.1007\/978-3-540-75520-3_24"},{"issue":"6","key":"1459_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1459_CR9","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: EC, pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"1459_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: EC, pp. 29\u201338 (2011)","DOI":"10.1145\/1993574.1993581"},{"key":"1459_CR11","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Sivan, B., Azar, Y.: Asymptotically optimal algorithm for stochastic adwords. In: EC, pp. 388\u2013404 (2012)","DOI":"10.1145\/2229012.2229043"},{"issue":"4","key":"1459_CR12","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1459_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theory Comput. 6(1), 247\u2013290 (2010)","journal-title":"Theory Comput."},{"key":"1459_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, J., Korula, N., Mirrokni, V.S., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: WINE, pp. 374\u2013385 (2009)","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"1459_CR15","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online stochastic matching: beating 1-1\/e. In: FOCS, pp. 117\u2013126 (2009)","DOI":"10.1109\/FOCS.2009.72"},{"key":"1459_CR16","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: FOCS, pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"issue":"2","key":"1459_CR17","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2014)","journal-title":"SIAM J. Comput."},{"key":"1459_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions\u2014II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"key":"1459_CR19","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, pp. 982\u2013991 (2008)"},{"key":"1459_CR20","doi-asserted-by":"crossref","unstructured":"Guruganesh, G.P., Singla, S.: Online matroid intersection: beating half for random arrival. In: IPCO, pp. 241\u2013253 (2017)","DOI":"10.1007\/978-3-319-59250-3_20"},{"key":"1459_CR21","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: WINE, pp. 170\u2013181 (2011)","DOI":"10.1007\/978-3-642-25510-6_15"},{"issue":"1\u20132","key":"1459_CR22","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1\u20132), 319\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"1459_CR23","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Post, I., Vondr\u00e1k, J.: Online submodular welfare maximization: greedy is optimal. In: SODA, pp. 1216\u20131225 (2013)","DOI":"10.1137\/1.9781611973105.88"},{"key":"1459_CR24","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: STOC, pp. 587\u2013596 (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"1459_CR25","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"1459_CR26","doi-asserted-by":"crossref","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: APPROX, pp. 231\u2013242 (2012)","DOI":"10.1007\/978-3-642-32512-0_20"},{"issue":"3","key":"1459_CR27","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1137\/15M1051142","volume":"47","author":"N Korula","year":"2018","unstructured":"Korula, N., Mirrokni, V.S., Zadimoghaddam, M.: Online submodular welfare maximization: greedy beats 1\/2 in random order. SIAM J. Comput. 47(3), 1056\u20131086 (2018)","journal-title":"SIAM J. Comput."},{"key":"1459_CR28","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: STOC, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"1459_CR29","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559\u2013573 (2012)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1459_CR30","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"5","key":"1459_CR31","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007)","journal-title":"J. ACM"},{"key":"1459_CR32","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Schapira, M., Vondr\u00e1k, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: EC, pp. 70\u201377 (2008)","DOI":"10.1145\/1386790.1386805"},{"key":"1459_CR33","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: AAAI, pp. 1812\u20131818 (2015)","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"1459_CR34","unstructured":"Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1\/2-approximation for submodular maximization on massive data streams. In: ICML, pp. 3826\u20133835 (2018)"},{"key":"1459_CR35","unstructured":"Zadimoghaddam, M.: Online weighted matching: beating the 1\/2 barrier. CoRR (2017). arXiv:1704.05384"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01459-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01459-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01459-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,9]],"date-time":"2022-10-09T20:34:21Z","timestamp":1665347661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01459-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,3]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1459"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01459-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,1,3]]},"assertion":[{"value":"21 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}