Document Open Access Logo

Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications

Authors Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.68.pdf
  • Filesize: 0.68 MB
  • 20 pages

Document Identifiers

Author Details

Hu Fu
  • ITCS, Shanghai University of Finance and Economics, China
Zhihao Gavin Tang
  • ITCS, Shanghai University of Finance and Economics, China
Hongxun Wu
  • IIIS, Tsinghua University, Beijing, China
Jinzhao Wu
  • Peking University, Beijing, China
Qianfan Zhang
  • IIIS, Tsinghua University, Beijing, China

Cite AsGet BibTex

Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.68

Abstract

With a wide range of applications, stochastic matching problems have been studied in different models, including prophet inequality, Query-Commit, and Price-of-Information. While there have been recent breakthroughs in all these settings for bipartite graphs, few non-trivial results are known for general graphs. In this paper, we study the random order vertex arrival contention resolution scheme for matching in general graphs, which is inspired by the recent work of Ezra et al. (EC 2020). We design an 8/15-selectable batched RCRS for matching and apply it to achieve 8/15-competitive/approximate algorithms for all the three models. Our results are the first non-trivial results for random order prophet matching and Price-of-Information matching in general graphs. For the Query-Commit model, our result substantially improves upon the 0.501 approximation ratio by Tang et al. (STOC 2020). We also show that no batched RCRS for matching can be better than 1/2+1/(2e²) ≈ 0.567-selectable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Matching
  • Contention Resolution Scheme
  • Price of Information
  • Query-Commit

Metrics

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

References

  1. Marek Adamczyk and Michal Wlodarczyk. Random order contention resolution schemes. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 790-801. IEEE Computer Society, 2018. Google Scholar
  2. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 512-521, 2011. Google Scholar
  3. Jonathan Aronson, Martin Dyer, Alan Frieze, and Stephen Suen. Randomized greedy matching. ii. Random Structures & Algorithms, 6(1):55-73, 1995. Google Scholar
  4. 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
  5. Simon Bruggmann and Rico Zenklusen. An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Mathematical Programming, pages 1-51, 2020. Google Scholar
  6. T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao. Ranking on arbitrary graphs: Rematch via continuous linear programming. SIAM J. Comput., 47(4):1529-1546, 2018. Google Scholar
  7. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320. ACM, 2010. Google Scholar
  8. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput., 43(6):1831-1879, 2014. Google Scholar
  9. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. In Automata, languages and programming. Part I, volume 5555 of Lecture Notes in Comput. Sci., pages 266-278. Springer, Berlin, 2009. Google Scholar
  10. Nikhil R. Devanur and Kamal Jain. Online matching with concave returns [extended abstract]. In STOC'12 - Proceedings of the 2012 ACM Symposium on Theory of Computing, pages 137-143. ACM, New York, 2012. Google Scholar
  11. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms, pages 700-714. SIAM, 2018. Google Scholar
  12. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. SIAM Journal on Discrete Mathematics, 31(3):1685-1701, 2017. Google Scholar
  13. Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In Péter Biró, Jason Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, pages 769-787. ACM, 2020. Google Scholar
  14. Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1014-1033. SIAM, 2016. Google Scholar
  15. Buddhima Gamlath, Sagar Kale, and Ola Svensson. Beating greedy for stochastic bipartite matching. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2841-2854. SIAM, 2019. Google Scholar
  16. Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The markovian price of information. In International Conference on Integer Programming and Combinatorial Optimization, pages 233-246. Springer, 2019. Google Scholar
  17. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Michel X. Goemans and José R. Correa, editors, Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings, volume 7801 of Lecture Notes in Computer Science, pages 205-216. Springer, 2013. Google Scholar
  18. Guru Guruganesh and Euiwoong Lee. Understanding the correlation gap for matchings. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018. Google Scholar
  19. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. Fully online matching. J. ACM, 67(3):17:1-17:25, 2020. Google Scholar
  20. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Fully online matching II: beating ranking and water-filling. In FOCS, pages 1380-1391. IEEE, 2020. Google Scholar
  21. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352-358. ACM, 1990. Google Scholar
  22. Robert D. Kleinberg, Bo Waggoner, and E. Glen Weyl. Descending price optimally coordinates search. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 23-24. ACM, 2016. Google Scholar
  23. Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 57:1-57:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  24. Brendan Lucier. An economic view of prophet inequalities. SIGecom Exch., 16(1):24-47, 2017. Google Scholar
  25. Aranyak Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci., 8(4):265-368, 2012. Google Scholar
  26. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. AdWords and generalized online matching. J. ACM, 54(5):Art. 22, 19, 2007. Google Scholar
  27. Sahil Singla. The price of information in combinatorial optimization. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2523-2532. SIAM, 2018. Google Scholar
  28. Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Towards a better understanding of randomized greedy matching. In STOC, pages 1097-1110. ACM, 2020. Google Scholar
  29. Martin L Weitzman. Optimal search for the best alternative. Econometrica: Journal of the Econometric Society, pages 641-654, 1979. 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 Imprint Privacy Contact