Perturbed Greedy on Oblivious Matching Problems
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang · arXiv (Cornell University) · 2019
We study the maximum matching problem in the oblivious setting, i.e. the edge set of the graph is unknown to the algorithm. The existence of an edge is revealed upon the probe of this pair of vertices. Further, if an edge exists between two probed vertices, then the edge must be included in the matching irrevocably. For unweighted graphs, the \textsf{Ranking} algorithm by Karp et al.~(STOC 1990) achieves approximation ratios $0.696$ for bipartite graphs and $0.526$ for general graphs. For vertex-weighted graphs, Chan et al. (TALG 2018) proposed a $0.501$-approximate algorithm. In contrast, the edge-weighted version only admits the trivial $0.5$-approximation by Greedy. In this paper, we propose the \textsf{Perturbed Greedy} algorithm for the edge-weighted oblivious matching problem and prove that it achieves a $0.501$ approximation ratio. Besides, we show that the approximation ratio of our algorithm on unweighted graphs is $0.639$ for bipartite graphs, and $0.531$ for general graphs. The later improves the state-of-the-art result by Chan et al. (TALG 2018). Furthermore, our algorithm can be regarded as a robust version of the \textsf{Modified Randomized Greedy} (MRG) algorithm. By implication, our $0.531$ approximation ratio serves as the first analysis of the MRG algorithm beyond the $(1/2+\epsilon)$ regime.