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 probecommit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downwardclosed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or timeout) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes nonuniform 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 11/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 11/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probecommit 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 ProbeCommit Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {46:146:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17168},
URN = {urn:nbn:de:0030drops171686},
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 