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
Go to the corresponding LIPIcs Volume Portal

Borodin, Allan ; MacRury, Calum ; Rakheja, Akash

Prophet Matching in the Probe-Commit Model

LIPIcs-APPROX46.pdf (0.8 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI