Donghao Zhu

List of Papers on the Online Matching Problem

Billy Jin and Donghao Zhu     (Update: 2023-3-25)

We have compiled a list of recent publications that address the online matching problem, covering both algorithmic and applied dimensions, with an emphasis on economics and management. These papers have been gathered from a variety of conferences (such as ACM EC, WINE, SODA, etc.) and journals (including Management Science, Operations Research, and Theoretical Economics, among others). Our goal is to share our humble reading experience without offering evaluations of the featured works. Overall, we believe these papers to be of high quality. We trust that this collection will serve as a valuable resource for examining the historical development of the online matching problem and guiding its future direction.

• 2022
  1. Itai Ashlagi, Afshin Nikzad and Philipp Strack. Matching in dynamic imbalanced markets. Review of Economic Studies, (forthcoming), 2022.
  2. Johannes Bäumler, Martin Bullinger, Stefan Kober and Donghao Zhu. High satisfaction in thin dynamic matching markets. Arvix, 2022.
  3. Jose H. Blanchet, Martin I. Reiman, Virag Shah, a Lawrence M. Wein and Linjia Wu. Asymptotically optimal control of a centralized dynamic matching market with general utilities. Operations Research, 70(6): 3355-3370, 2022.
  4. Süleyman Kerimov, Itai Ashlagi and Itai Gurvich. On the optimality of greedy policies in dynamic matching. ACM EC, 2022.
  5. Jacob D. Leshno. Dynamic matching in overloaded waiting lists. American Economic Review, 112(12): 3876-3910, 2022.
  6. Marco Pavone, Amin Saberi, Maximilian Schiffer and Matt Wu Tsao. Online hypergraph matching with delays. Operations Research, 2022.
• 2021
  1. Ishan Agarwal, Richard Cole, and Yixin Tao. Selecting a match: exploration vs decision. Arxiv, 2021.
  2. Angelos Aveklouris, Levi DeValve and Amy R. Ward. Matching impatient and heterogeneous demand and supply. Arxiv, 2021.
  3. Billy Jin and David P. Williamson. Improved analysis of RANKING for online vertex-weighted bipartite matching ACM WINE, 2021.
  4. Naonori Kakimura and Donghao Zhu. Dynamic bipartite matching market with arrivals and departures. ACM WINE, 2021.
• 2020
  1. Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Thickness and information in dynamic matching markets. Journal of Political Economy, 128(3):783-815, 2020.
  2. Mariagiovanna Baccara, SangMok Lee, and Leeat Yariv. Optimal dynamic matching. Theoretical Economics, 15(3):1221-1278, 2020.
  3. Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown and Brendan Lucier. Dynamic weighted matching with heterogeneous arrival and departure rates. ACM WINE, 2020.
  4. Nick Gravin, Zhihao Gavin Tang, and Kangning Wang. Online Stochastic Matching with Edge Arrivals. Arxiv, 2020.
  5. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang. Fully online matching ii: Beating ranking and water-filling. FOCS, 2020.
  6. Jun Li and Serguei Netessine. Higher market thickness reduces matching rate in online platform: Evidence from a quasiexperiment. Management Science, 66(1):271-289, 2020.
  7. Panayotis Mertikopoulos, Heinrich H. Nax and Bary S. R. Pradelski. Quick or cheap? Breaking points in dynamic markets. ACM EC, 2020.
  8. Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Towards a better understanding of randomized greedy matching. ACM STOC, 2020.
• 2019
  1. Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi and Chris Sholley. Edge weighted online windowed matching. ACM EC, 2019.
  2. Itai Ashlagi, Maximilien Burq, Patrick Jaillet, and Vahideh Manshadi. On matching and thickness in heterogeneous dynamic markets. Operations Research, 67(4):927-949, 2019.
  3. Jessica Fong. Effects of market size and competition in two-sided markets: evidence from online dating. SSCN, 2019.
  4. Buddhima Gamlath, Mikhail Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. FOCS, 2019.
  5. Zhiyi Huang. Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Weighted Case Arxiv, 2019.
  6. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals ACM Transactions on Algorithms, 15(3): 1-15, 2019.
• 2018
  1. Itai Ashlagi, Adam Bingaman, Maximilien Burq, Vahideh Manshadi, David Gamarnik, Cathi Murphey, Alvin E. Roth, Marc L. Melcher and Michael A. Rees. Effect of match-run frequencies on the number of transplants and waiting times in kidney exchange. American Journal of Transplantation, 18(5):1177-1186, 2018.
  2. Ilan Reuven Cohen and David Wajc. Randomized online matching in regular graphs. SODA, 2018.
  3. Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. SODA, 2018.
• 2017
  1. Ross Anderson, Itai Ashlagi, David Gamarnik and Yash Kanoria. Efficient dynamic barter exchange. Operations Research, 2017.
• 2016
  1. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. New algorithms, better bounds, and a novel model for online stochastic matching. ESA, 2016.
  2. Yuval Emek, Shay Kutten and Roger Wattenhofer. Online matching: haste makes waste! ACM STOC, 2016.
• 2015
  1. Guru Prashanth Guruganesh and Sahil Singla. Online matroid intersection: Beating half for random arrival. IPCO, 2017.
• 2014
  1. Mariagiovanna Baccara, Allan Collard-Wexler, Leonardo Felli and Leeat Yariv. Child-adoption matching: Preferences for gender and race. American Economic Journal: Applied Economics, 6(3):133-58, 2014.
  2. Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3):624-646, 2014.
• 2013
  1. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. ACM SODA, 2013.
  2. Aranyak Mehta. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4):265-368, 2013.
  3. Baharak Rastegari， Anne Condon， Nicole Immorlica and Kevin Leyton-Brown. Two-sided matching with partial information. ACM EC, 2013.
• 2012
  1. Vahideh H. Manshadi, Shayan Oveis Gharan and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4):559-573, 2012.
• 2011
  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande and Aranyak Mehta. Online bipartite matching with unknown distributions. ACM SODA, 2011.
  2. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online vertex-weighted bipartite matching and single-bid budgeted allocations. ACM STOC, 2011.
  3. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals. ACM STOC, 2011.
• 2010
  1. M. Utku Ünver. Dynamic kidney exchange. The Review of Economic Studies, 77(1):372-414, 2010.
• 2009
  1. Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. FOCS, 2009.
• 2007
  1. Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. ESA, 2007.
  2. Aranyak Mehta, Amin Saberi, Umesh Vazirani and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM, 54(5):22-es, 2007.
• 2005
  1. Alvin E. Roth, Tayfun Sönmez and M. Utku Ünver. Pairwise kidney exchange. Journal of Economic Theory, 125(2):151-188, 2005.
• 2001
  1. Robert Shimer and Lones Smith. Matching, search, and heterogeneity. The BE Journal of Macroeconomics, 1(1), 2001.
• 1990
  1. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. ACM STOC, 1990.

We hope you enjoy reading these papers. As our reading expands, we will continue to update the list with additional papers we come across. Should you be aware of any relevant papers not mentioned here, please don't hesitate to contact us, and we will update the list at a random time. ;)