Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience

Brian Brubach, Nathaniel Grammel, Will Ma, Aravind Srinivasan
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2872-2880, 2021.

Abstract

We study several generalizations of the Online Bipartite Matching problem. We consider settings with stochastic rewards, patience constraints, and weights (considering both vertex- and edge-weighted variants). We introduce a stochastic variant of the patience-constrained problem, where the patience is chosen randomly according to some known distribution and is not known in advance. We also consider stochastic arrival settings (i.e. the nature in which the online vertices arrive is determined by a known random process), which are natural settings that are able to beat the hard worst-case bounds of adversarial arrivals. We design black-box algorithms for star graphs under various models of patience, which solve the problem optimally for deterministic or geometrically-distributed patience, and yield a 1/2-approximation for any patience distribution. These star graph algorithms are then used as black boxes to solve the online matching problems under different arrival settings. We show improved (or first-known) competitive ratios for these problems. We also present negative results that include formalizing the concept of a stochasticity gap for LP upper bounds on these problems, showing some new stochasticity gaps for popular LPs, and bounding the worst-case performance of some greedy approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-brubach21a, title = { Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience }, author = {Brubach, Brian and Grammel, Nathaniel and Ma, Will and Srinivasan, Aravind}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2872--2880}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/brubach21a/brubach21a.pdf}, url = {https://proceedings.mlr.press/v130/brubach21a.html}, abstract = { We study several generalizations of the Online Bipartite Matching problem. We consider settings with stochastic rewards, patience constraints, and weights (considering both vertex- and edge-weighted variants). We introduce a stochastic variant of the patience-constrained problem, where the patience is chosen randomly according to some known distribution and is not known in advance. We also consider stochastic arrival settings (i.e. the nature in which the online vertices arrive is determined by a known random process), which are natural settings that are able to beat the hard worst-case bounds of adversarial arrivals. We design black-box algorithms for star graphs under various models of patience, which solve the problem optimally for deterministic or geometrically-distributed patience, and yield a 1/2-approximation for any patience distribution. These star graph algorithms are then used as black boxes to solve the online matching problems under different arrival settings. We show improved (or first-known) competitive ratios for these problems. We also present negative results that include formalizing the concept of a stochasticity gap for LP upper bounds on these problems, showing some new stochasticity gaps for popular LPs, and bounding the worst-case performance of some greedy approaches. } }
Endnote
%0 Conference Paper %T Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience %A Brian Brubach %A Nathaniel Grammel %A Will Ma %A Aravind Srinivasan %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-brubach21a %I PMLR %P 2872--2880 %U https://proceedings.mlr.press/v130/brubach21a.html %V 130 %X We study several generalizations of the Online Bipartite Matching problem. We consider settings with stochastic rewards, patience constraints, and weights (considering both vertex- and edge-weighted variants). We introduce a stochastic variant of the patience-constrained problem, where the patience is chosen randomly according to some known distribution and is not known in advance. We also consider stochastic arrival settings (i.e. the nature in which the online vertices arrive is determined by a known random process), which are natural settings that are able to beat the hard worst-case bounds of adversarial arrivals. We design black-box algorithms for star graphs under various models of patience, which solve the problem optimally for deterministic or geometrically-distributed patience, and yield a 1/2-approximation for any patience distribution. These star graph algorithms are then used as black boxes to solve the online matching problems under different arrival settings. We show improved (or first-known) competitive ratios for these problems. We also present negative results that include formalizing the concept of a stochasticity gap for LP upper bounds on these problems, showing some new stochasticity gaps for popular LPs, and bounding the worst-case performance of some greedy approaches.
APA
Brubach, B., Grammel, N., Ma, W. & Srinivasan, A.. (2021). Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2872-2880 Available from https://proceedings.mlr.press/v130/brubach21a.html.

Related Material