Borodin, Allan ;
MacRury, Calum ;
Rakheja, Akash
Secretary Matching Meets Probing with Commitment
Abstract
We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the onesided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e β E}, and G has edge weights (w_{e})_{e β E} or vertex weights (w_u)_{u β U}. Additionally, G has a downwardclosed set of probing constraints (π_{v})_{v β V}, where π_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each π_v.
In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of π_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 11/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for nonvanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each π_v corresponds to a patience constraint π_v (i.e., π_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 11/e.
 When the offline vertices are unweighted.
 When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) β E.
 When the patience constraint π_v satisfies π_v β {[1,U} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.
BibTeX  Entry
@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2021.13,
author = {Borodin, Allan and MacRury, Calum and Rakheja, Akash},
title = {{Secretary Matching Meets Probing with Commitment}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {13:113:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14706},
URN = {urn:nbn:de:0030drops147067},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.13},
annote = {Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty}
}
15.09.2021
Keywords: 

Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 