Timezone: »

 
Poster
Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes
Brian Brubach · Nathaniel Grammel · Will Ma · Aravind Srinivasan

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a $0.382$-approximate algorithm, significantly improving over the previous best $0.31$-approximation of Baveja et al. (2018). When the vertices do not have patience constraints, we describe a $0.432$-approximate random order probing algorithm with several corollaries such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show a $0.632$-approximate algorithm that improves on the recent $1/3$-guarantee of Hikima et al. (2021).
Keywords: Optimization · Graph Learning

Author Information

Brian Brubach (Wellesley College)
Nathaniel Grammel (University of Maryland, College Park)
Will Ma (Columbia University)
Aravind Srinivasan (University of Maryland College Park)

Aravind Srinivasan is a Professor with the Department of Computer Science and UMIACS at UMD, College Park. He received his undergraduate degree from the Indian Institute of Technology, Madras, and his Ph.D. from Cornell University. He was a postdoctoral researcher at the Institute for Advanced Study in Princeton and at DIMACS. Srinivasan's research interests are in randomized algorithms, E-commerce, public health, networking, social networks, and combinatorial optimization, as well as in the growing confluence of algorithms, networks, and randomness, in fields including the social Web, machine learning, biology, and energy. He has published more than 115 papers in these areas, in fora including Nature, Journal of the ACM, IEEE/ACM Transactions on Networking, and the SIAM Journal on Computing. He is Editor-in-Chief of the ACM Transactions on Algorithms, Managing Editor for Theory of Computing, and Associate Editor of Networks. Srinivasan is a Fellow of four professional societies: ACM, AAAS, IEEE and EATCS. He received a Distinguished Alumnus Award from his alma mater IIT Madras. He also received the Distinguished Faculty Award from the Board of Visitors of the College of Computing, Mathematical, and Natural Sciences (University of Maryland) in 2016. He received a Data Science Research Award from Adobe, Inc. in 2017.

More from the Same Authors