论文标题
二分随机匹配：在线，随机订单和I.I.D.型号
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models
论文作者
论文摘要
在随机探测的背景下，我们考虑在线随机匹配问题。也就是说，基于已知的边缘概率，必须探测与在线节点相邻的边缘以确定它们是否存在的单方面双方匹配问题。如果存在探测的边缘，则必须在匹配（如果可能的话）中使用。我们在耐心（或预算）约束的一般性中研究了这个问题，这限制了可以对在线节点附近的边缘进行的探针的数量。耐心的限制导致在特殊耐心和充分（即无限）耐心的特殊情况下未遇到的建模和计算效率问题。随机匹配的问题导致各种设置。我们的主要贡献是提供一种新的LP松弛和统一的方法，以在三种不同的输入模型设置（即对对抗性，随机秩序和已知的I.I.D.）中建立新的和改进的竞争界限。在所有这些设置中，该算法对在线节点的排序没有任何控制。我们在这些环境中建立竞争界限，当不需要探测边缘时（即确定存在）时，所有这些界限都将标准的非策略设置概括。我们所有的竞争比率都符合任意边缘概率和耐心限制： （1）$ 1-1/e $比率在知道随机图时，离线顶点是加权的，在线到达是对手的。 （2）$ 1-1/e $比率在知道随机图时，边缘加权并以随机顺序给出在线到达（即，在ROM，随机顺序模型中）。 （3）在在线到达时，$ 1-1/e $比率I.I.D.从已知的随机类型图和边缘加权。 （4）a（紧密）$ 1/e $比率当随机图未知时，边缘加权并以随机顺序给出在线到达。
Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist, based on known edge probabilities. If a probed edge exists, it must be used in the matching (if possible). We study this problem in the generality of a patience (or budget) constraint which limits the number of probes that can be made to edges adjacent to an online node. The patience constraint results in modelling and computational efficiency issues that are not encountered in the special cases of unit patience and full (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d.). In all these settings, the algorithm does not have any control on the ordering of the online nodes. We establish competitive bounds in these settings, all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty). All of our competitive ratios hold for arbitrary edge probabilities and patience constraints: (1) A $1-1/e$ ratio when the stochastic graph is known, offline vertices are weighted and online arrivals are adversarial. (2) A $1-1/e$ ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A $1-1/e$ ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) $1/e$ ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order.
