{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:55Z","timestamp":1770994075506,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T00:00:00Z","timestamp":1584057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2017-06551"],"award-info":[{"award-number":["RGPIN-2017-06551"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>We perform an experimental study of algorithms for online bipartite matching under the known i.i.d input model with integral types. In the last decade, there has been substantial effort in designing complex algorithms to improve worst-case approximation ratios. Our goal is to determine how these algorithms perform on more practical instances rather than worst-case instances. In particular, we are interested in whether the ranking of the algorithms by their worst-case performance is consistent with the ranking of the algorithms by their average-case\/practical performance. We are also interested in whether preprocessing times and implementation difficulties that are introduced by these algorithms are justified in practice. To that end, we evaluate these algorithms on different random inputs as well as real-life instances obtained from publicly available repositories. We compare these algorithms against several simple greedy-style algorithms. Most of the complex algorithms in the literature are presented as being non-greedy (i.e., an algorithm can intentionally skip matching a node that has available neighbors) to simplify the analysis. Every such algorithm can be turned into a greedy one without hurting its worst-case performance. On our benchmarks, non-greedy versions of these algorithms perform much worse than their greedy versions. Greedy versions perform about as well as the simplest greedy algorithm by itself. This, together with our other findings, suggests that simplest greedy algorithms are competitive with the state-of-the-art worst-case algorithms for online bipartite matching on many average-case and practical input families. Greediness is by far the most important property of online algorithms for bipartite matching.<\/jats:p>","DOI":"10.1145\/3379552","type":"journal-article","created":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T12:03:13Z","timestamp":1584100993000},"page":"1-37","source":"Crossref","is-referenced-by-count":11,"title":["An Experimental Study of Algorithms for Online Bipartite Matching"],"prefix":"10.1145","volume":"25","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Christodoulos","family":"Karavasilis","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Denis","family":"Pankratov","sequence":"additional","affiliation":[{"name":"Concordia University, Montreal, QC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2020,3,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2018"},{"key":"e_1_2_1_2_1","volume-title":"Online Bipartite Matching Library. Retrieved","author":"Pankratov Denis","year":"2018"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_15"},{"key":"e_1_2_1_4_1","volume-title":"Probability 8 Computing 21, 5","author":"Bilu Yonatan","year":"2012"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Greedy bipartite matching in random type Poisson arrival model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"2018","author":"Borodin A.","year":"2018","journal-title":"APPROX\/RANDOM"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","volume-title":"On conceptually simple algorithms for variants of online bipartite matching","author":"Borodin Allan","DOI":"10.1007\/978-3-319-89441-6_19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Joan Boyar Lene M. Favrholdt Christian Kudahl Kim S. Larsen and Jesper W. Mikkelsen. [n.d.]. Online algorithms with advice: A survey. ACM Comput. Surv. 50 2 ([n.\u00a0d.]) 19:1--19:34.  Joan Boyar Lene M. Favrholdt Christian Kudahl Kim S. Larsen and Jesper W. Mikkelsen. [n.d.]. Online algorithms with advice: A survey. ACM Comput. Surv. 50 2 ([n.\u00a0d.]) 19:1--19:34.","DOI":"10.1145\/3056461"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"New algorithms, better bounds, and a novel model for online stochastic matching","volume":"24","author":"Brubach Brian","year":"2016","journal-title":"Proc. of ESA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297140"},{"key":"e_1_2_1_10_1","volume-title":"Kleinberg","author":"Devanur Nikhil R.","year":"2013"},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"On the power of advice and randomization for online bipartite matching","volume":"37","author":"D\u00fcrr Christoph","year":"2016","journal-title":"Proc. of ESA."},{"key":"e_1_2_1_12_1","volume-title":"FOCS","author":"Feldman Jon","year":"2009"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of SODA. 982--991","author":"Goel Gagan","year":"2008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_2_1_16_1","volume-title":"22nd Annual Symposium on Foundations of Computer Science","author":"Richard","year":"1981"},{"key":"e_1_2_1_17_1","volume-title":"Proc. of STOC. 352--358","author":"Karp R. M."},{"key":"e_1_2_1_18_1","volume-title":"Heuristic initialization for bipartite matching problems. ACM Journal of Experimental Algorithmics 15","author":"Langguth Johannes","year":"2010"},{"key":"e_1_2_1_19_1","volume-title":"Greedy matching algorithms, an experimental study. ACM Journal of Experimental Algorithms 3","author":"Magun Jacob","year":"1998"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.98"},{"key":"e_1_2_1_22_1","unstructured":"A. Mastin and P. Jaillet. 2013. Greedy online bipartite matching on random graphs. ArXiv e-prints (July 2013). arxiv:cs.DS\/1307.2536  A. Mastin and P. Jaillet. 2013. Greedy online bipartite matching on random graphs. ArXiv e-prints (July 2013). arxiv:cs.DS\/1307.2536"},{"key":"e_1_2_1_23_1","first-page":"265","article-title":"Online matching and ad allocation","volume":"8","author":"Mehta A.","year":"2012","journal-title":"Theoretical Computer Science"},{"key":"e_1_2_1_24_1","volume-title":"A critical point for random graphs with a given degree sequence. Random Structures 8 Algorithms 6, 2--3","author":"Michael Molloy","year":"1995"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.012582999"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.10.015"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence. http:\/\/networkrepository.com.","author":"Ryan"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.3.828"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562785"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379552","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379552","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:23Z","timestamp":1750197743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379552"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,13]]},"references-count":29,"alternative-id":["10.1145\/3379552"],"URL":"https:\/\/doi.org\/10.1145\/3379552","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,13]]}}}