Abstract

Online stochastic matching is a model in which we know an i.i.d. distribution for online vertices and need to match each online vertex immediately and irrevocably. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. We introduce two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting. For edge-weighted matching with free disposal, We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality.

Biography

Shuyi Yan is an undergraduate in Yao Class, Tsinghua University. His research interests lie in theoretical computer science, especially in algorithms and complexity.

• Admission

Tencent ID: 935-154-875