Document Open Access Logo

Online Stochastic Matching with Edge Arrivals

Authors Nick Gravin, Zhihao Gavin Tang, Kangning Wang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.74.pdf
  • Filesize: 0.92 MB
  • 20 pages

Document Identifiers

Author Details

Nick Gravin
  • ITCS, Shanghai University of Finance and Economics, China
Zhihao Gavin Tang
  • ITCS, Shanghai University of Finance and Economics, China
Kangning Wang
  • Department of Computer Science, Duke University, Durham, NC, USA

Funding

This work is supported by Science and Technology Innovation 2030 - "New Generation of Artificial Intelligence" Major Project No.(2018AAA0100903), National Natural Science Foundation of China (NSFC) grant 61932002, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE), Fundamental Research Funds for the Central Universities.
  • Tang, Zhihao Gavin: supported by NSFC grant 61902233.
  • Wang, Kangning: supported by NSF grant CCF-1637397 and ONR grant N00014-19-1-2268.

Cite As Get BibTex

Nick Gravin, Zhihao Gavin Tang, and Kangning Wang. Online Stochastic Matching with Edge Arrivals. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 74:1-74:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.74

Abstract

Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by Gamlath et al., who showed that no online policy is better than the straightforward greedy algorithm, i.e., no online algorithm has a worst-case competitive ratio better than 0.5. In this work, we consider the bipartite matching problem with edge arrivals in a natural stochastic framework, i.e., Bayesian setting where each edge of the graph is independently realized according to a known probability distribution. 
We focus on a natural class of prune & greedy online policies motivated by practical considerations from a multitude of online matching platforms. Any prune & greedy algorithm consists of two stages: first, it decreases the probabilities of some edges in the stochastic instance and then runs greedy algorithm on the pruned graph. We propose prune & greedy algorithms that are 0.552-competitive on the instances that can be pruned to a 2-regular stochastic bipartite graph, and 0.503-competitive on arbitrary stochastic bipartite graphs. The algorithms and our analysis significantly deviate from the prior work. We first obtain analytically manageable lower bound on the size of the matching, which leads to a non-linear optimization problem. We further reduce this problem to a continuous optimization with a constant number of parameters that can be solved using standard software tools.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Mathematical optimization
  • Mathematics of computing → Graph algorithms
Keywords
  • online matching
  • graph algorithms
  • prophet inequality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. Improved approximation algorithms for stochastic matching. In ESA, volume 9294 of Lecture Notes in Computer Science, pages 1-12. Springer, 2015. Google Scholar
  2. Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Edge weighted online windowed matching. In EC, pages 729-742. ACM, 2019. Google Scholar
  3. Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 170-181. Springer, 2010. Google Scholar
  4. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012. Google Scholar
  5. Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu. Improved bounds in stochastic matching and optimization. Algorithmica, 80(11):3225-3252, 2018. Google Scholar
  6. Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. ACM SIGACT News, 39(1):80-87, 2008. Google Scholar
  7. Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA, volume 4698 of Lecture Notes in Computer Science, pages 253-264. Springer, 2007. Google Scholar
  8. Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online algorithms for maximum cardinality matching with edge arrivals. Algorithmica, 81(5):1781-1799, 2019. Google Scholar
  9. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. In ICALP (1), volume 5555 of Lecture Notes in Computer Science, pages 266-278. Springer, 2009. Google Scholar
  10. Ilan Reuven Cohen and David Wajc. Randomized online matching in regular graphs. In SODA '18, pages 960-979. SIAM, 2018. Google Scholar
  11. Kevin P. Costello, Prasad Tetali, and Pushkar Tripathi. Stochastic matching with commitment. In ICALP (1), volume 7391 of Lecture Notes in Computer Science, pages 822-833. Springer, 2012. Google Scholar
  12. Nikhil R. Devanur and Kamal Jain. Online matching with concave returns. In STOC, pages 137-144. ACM, 2012. Google Scholar
  13. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In SODA, pages 101-107. SIAM, 2013. Google Scholar
  14. Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved bounds for online preemptive matching. In STACS, volume 20 of LIPIcs, pages 389-399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  15. Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In EC '20, pages 769-787. ACM, 2020. Google Scholar
  16. Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. In FOCS, pages 117-126. IEEE Computer Society, 2009. Google Scholar
  17. Buddhima Gamlath, Sagar Kale, and Ola Svensson. Beating greedy for stochastic bipartite matching. In SODA, pages 2841-2854. SIAM, 2019. Google Scholar
  18. Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. In FOCS, pages 26-37. IEEE Computer Society, 2019. Google Scholar
  19. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, pages 982-991, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347189.
  20. Nikolai Gravin and Hongao Wang. Prophet inequality for bipartite matching: Merits of being simple and non adaptive. In EC, pages 93-109. ACM, 2019. Google Scholar
  21. Guru Prashanth Guruganesh and Sahil Singla. Online matroid intersection: Beating half for random arrival. In IPCO, volume 10328 of Lecture Notes in Computer Science, pages 241-253. Springer, 2017. Google Scholar
  22. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In STOC, pages 17-29. ACM, 2018. Google Scholar
  23. 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. In SODA, pages 2875-2886. SIAM, 2019. Google Scholar
  24. Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Math. Oper. Res., 39(3):624-646, 2014. Google Scholar
  25. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In STOC, pages 587-596, 2011. Google Scholar
  26. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352-358, 1990. Google Scholar
  27. Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games and Economic Behavior, 113:97-115, 2019. Google Scholar
  28. László Lovász and Michael D Plummer. Matching theory. Providence, R.I. : AMS Chelsea Pub, 2009. Originally published: Amsterdam; New York : North-Holland, 1986. URL: https://ebookcentral.proquest.com/lib/qut/detail.action?docID=4832190.
  29. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In STOC, pages 597-606, 2011. Google Scholar
  30. Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res., 37(4):559-573, 2012. Google Scholar
  31. Andrew McGregor. Finding graph matchings in data streams. In APPROX-RANDOM, volume 3624 of Lecture Notes in Computer Science, pages 170-181. Springer, 2005. Google Scholar
  32. Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265-368, 2013. Google Scholar
  33. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007. Google Scholar
  34. Joseph (Seffi) Naor and David Wajc. Near-optimum online ad allocation for targeted advertising. ACM Trans. Economics and Comput., 6(3-4):16:1-16:20, 2018. Google Scholar
  35. Ashwinkumar Badanidiyuru Varadaraja. Buyback problem - approximate matroid intersection with cancellation costs. In ICALP (1), volume 6755 of Lecture Notes in Computer Science, pages 379-390. Springer, 2011. Google Scholar
  36. Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In ICALP (1), volume 9134 of Lecture Notes in Computer Science, pages 1070-1081. Springer, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact