{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:24:27Z","timestamp":1764937467591,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T00:00:00Z","timestamp":1664323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T00:00:00Z","timestamp":1664323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72071157","71732006"],"award-info":[{"award-number":["72071157","71732006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2016M592811"],"award-info":[{"award-number":["2016M592811"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["754462"],"award-info":[{"award-number":["754462"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72192834"],"award-info":[{"award-number":["72192834"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00916-4","type":"journal-article","created":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T19:02:37Z","timestamp":1664391757000},"page":"3611-3640","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Learn from history for online bipartite matching"],"prefix":"10.1007","volume":"44","author":[{"given":"Huili","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Rui","family":"Du","sequence":"additional","affiliation":[]},{"given":"Kelin","family":"Luo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9815-2330","authenticated-orcid":false,"given":"Weitian","family":"Tong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,28]]},"reference":[{"key":"916_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: SODA, pp 1253\u20131264","DOI":"10.1137\/1.9781611973082.95"},{"key":"916_CR2","doi-asserted-by":"crossref","unstructured":"Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. In: ESA, pp 170\u2013181","DOI":"10.1007\/978-3-642-15775-2_15"},{"issue":"1","key":"916_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3379552","volume":"25","author":"A Borodin","year":"2020","unstructured":"Borodin A, Karavasilis C, Pankratov D (2020) An experimental study of algorithms for online bipartite matching. J Exp Algorithmics 25(1):1\u201337","journal-title":"J Exp Algorithmics"},{"key":"916_CR4","unstructured":"Brubach B, Sankararaman KA, Srinivasan A, Xu P (2016) Online stochastic matching: New algorithms and bounds. In: ESA, pp 1\u201316"},{"issue":"2","key":"916_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.ejor.2015.06.029","volume":"247","author":"XA Chen","year":"2015","unstructured":"Chen XA, Wang Z (2015) A dynamic learning algorithm for online matching problems with concave returns. Eur J Oper Res 247(2):379\u2013388","journal-title":"Eur J Oper Res"},{"key":"916_CR6","doi-asserted-by":"crossref","unstructured":"Devanur N R, Jain K, Kleinberg R (2013) Randomized primal-dual analysis of ranking for online bipartite matching. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, pp 101\u2013107","DOI":"10.1137\/1.9781611973105.7"},{"key":"916_CR7","doi-asserted-by":"crossref","unstructured":"Dickerson J P, Sankararaman K A, Srinivasan A, Xu P (2018) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. In: AAAI, pp 1007\u20131014","DOI":"10.1609\/aaai.v32i1.11477"},{"key":"916_CR8","unstructured":"DIDI (2016) Gaia open dataset"},{"issue":"3\u20134","key":"916_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3105446","volume":"6","author":"H Esfandiari","year":"2018","unstructured":"Esfandiari H, Korula N, Mirrokni V (2018) Allocation with traffic spikes: mixing adversarial and stochastic models. ACM Trans Econ Comput 6(3\u20134):1\u201323","journal-title":"ACM Trans Econ Comput"},{"key":"916_CR10","doi-asserted-by":"crossref","unstructured":"Fahrbach M, Huang Z, Tao R, Zadimoghaddam M (2020) Edge-weighted online bipartite matching. CoRR, arXiv:2005.01929","DOI":"10.1109\/FOCS46700.2020.00046"},{"key":"916_CR11","doi-asserted-by":"crossref","unstructured":"Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1\/e. In: FOCS, pp 117\u2013126","DOI":"10.1109\/FOCS.2009.72"},{"key":"916_CR12","first-page":"982","volume":"8","author":"G Goel","year":"2008","unstructured":"Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. SODA 8:982\u2013991","journal-title":"SODA"},{"key":"916_CR13","doi-asserted-by":"crossref","unstructured":"Haeupler B, Mirrokni V S, Zadimoghaddam M (2011) Online stochastic weighted matching: Improved approximation algorithms. In: International workshop on internet and network economics, pp 170\u2013181","DOI":"10.1007\/978-3-642-25510-6_15"},{"issue":"3","key":"916_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3326169","volume":"15","author":"Z Huang","year":"2019","unstructured":"Huang Z, Tang ZG, Wu X, Zhang Y (2019) Online vertex-weighted bipartite matching: Beating 1\u20131\/e with random arrivals. ACM Trans Algorithms (TALG) 15(3):1\u201315","journal-title":"ACM Trans Algorithms (TALG)"},{"issue":"3","key":"916_CR15","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1287\/moor.2013.0621","volume":"39","author":"P Jaillet","year":"2014","unstructured":"Jaillet P, Lu X (2014) Online stochastic matching: New algorithms with better bounds. Math Oper Res 39(3):624\u2013646","journal-title":"Math Oper Res"},{"issue":"1","key":"916_CR16","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 KR (2000) An optimal deterministic algorithm for online b-matching. Theor Comput Sci 233(1):319\u2013325","journal-title":"Theor Comput Sci"},{"key":"916_CR17","doi-asserted-by":"crossref","unstructured":"Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. In: SODA, pp 2082\u20132095","DOI":"10.1137\/1.9781611975994.128"},{"key":"916_CR18","doi-asserted-by":"crossref","unstructured":"Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. In: STOC, pp 587-596","DOI":"10.1145\/1993636.1993715"},{"key":"916_CR19","doi-asserted-by":"crossref","unstructured":"Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. In: STOC, pp 352\u2013358","DOI":"10.1145\/100216.100262"},{"key":"916_CR20","doi-asserted-by":"crossref","unstructured":"Kesselheim T, Radke K, T\u00f6nnis A, V\u00f6cking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: ESA, pp 589\u2013600","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"916_CR21","doi-asserted-by":"crossref","unstructured":"Korula N, P\u00e1l M (2009) Algorithms for secretary problems on graphs and hypergraphs. In: ICALP, pp 508\u2013520","DOI":"10.1007\/978-3-642-02930-1_42"},{"issue":"1\u20132","key":"916_CR22","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Quart 2(1\u20132):83\u201397","journal-title":"Naval Res Logist Quart"},{"key":"916_CR23","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.cor.2016.05.004","volume":"75","author":"A Legrain","year":"2016","unstructured":"Legrain A, Jaillet P (2016) A stochastic algorithm for online bipartite resource allocation problems. Comput Oper Res 75:28\u201337","journal-title":"Comput Oper Res"},{"key":"916_CR24","doi-asserted-by":"crossref","unstructured":"Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: STOC, pp 597\u2013606","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"916_CR25","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: online actions based on offline statistics. Math Oper Res 37(4):559\u2013573","journal-title":"Math Oper Res"},{"issue":"4","key":"916_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta A (2013) Online matching and ad allocation. Found Trends Theor Comput Sci 8(4):265\u2013368","journal-title":"Found Trends Theor Comput Sci"},{"issue":"3","key":"916_CR27","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/s10878-016-0100-2","volume":"34","author":"X Sun","year":"2017","unstructured":"Sun X, Zhang J, Zhang J (2017) Near optimal algorithms for online weighted bipartite matching in adversary model. J Comb Optim 34(3):689\u2013705","journal-title":"J Comb Optim"},{"key":"916_CR28","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.tcs.2015.05.032","volume":"607","author":"H-F Ting","year":"2015","unstructured":"Ting H-F, Xiang X (2015) Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching. Theor Comput Sci 607:247\u2013256","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00916-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00916-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00916-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:41:18Z","timestamp":1667036478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00916-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,28]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["916"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00916-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,9,28]]},"assertion":[{"value":"19 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The code generated during the current study is available from the corresponding author on reasonable request.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}