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.APPROX/RANDOM.2022.46
URN: urn:nbn:de:0030-drops-171686
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17168/
Borodin, Allan ;
MacRury, Calum ;
Rakheja, Akash
Prophet Matching in the Probe-Commit Model
Abstract
We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or time-out) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish the following competitive ratio results against the offline adaptive benchmark:
1) A tight 1/2 ratio when the arrival ordering π is chosen adversarially.
2) A 1-1/e ratio when the arrival ordering π is chosen u.a.r. (uniformly at random). If π is generated adversarially, we generalize the prophet inequality matching problem. If π is u.a.r., we generalize the prophet secretary matching problem. Both results improve upon the previous best competitive ratio of 0.46 in the more restricted known i.i.d. (independent and identically distributed) arrival model against the standard offline adaptive benchmark due to Brubach et al. We are the first to study the prophet secretary matching problem in the context of probing, and our 1-1/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probe-commit problem, where we match the best known result due to Gamlath et al.
BibTeX - Entry
@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2022.46,
author = {Borodin, Allan and MacRury, Calum and Rakheja, Akash},
title = {{Prophet Matching in the Probe-Commit Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {46:1--46:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17168},
URN = {urn:nbn:de:0030-drops-171686},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.46},
annote = {Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty}
}
|
Keywords: |
|
Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
15.09.2022 |
