Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

Huang, ZY; Tang, ZHG; Wu, XW; Zhang, YH

Huang, ZY (reprint author), Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China.

ACM TRANSACTIONS ON ALGORITHMS, 2019; 15 (3):

Abstract

We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighte......

Full Text Link


Links

期刊讨论 | 中国SCI论文 | 期刊主页 | 投稿经验 | 杂志官网 | 投稿链接 | 作者需知 | PMC链接 | Pubmed全文检索