License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.74
URN: urn:nbn:de:0030-drops-141438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14143/
Gravin, Nick ;
Tang, Zhihao Gavin ;
Wang, Kangning
Online Stochastic Matching with Edge Arrivals
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.
BibTeX - Entry
@InProceedings{gravin_et_al:LIPIcs.ICALP.2021.74,
author = {Gravin, Nick and Tang, Zhihao Gavin and Wang, Kangning},
title = {{Online Stochastic Matching with Edge Arrivals}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {74:1--74:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14143},
URN = {urn:nbn:de:0030-drops-141438},
doi = {10.4230/LIPIcs.ICALP.2021.74},
annote = {Keywords: online matching, graph algorithms, prophet inequality}
}
|
Keywords: |
|
online matching, graph algorithms, prophet inequality |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
