23 citations · 58 across the 13 of their papers we have counts for
3 papers · 1 filter
Sublinear Time Algorithm for Online Weighted Bipartite Matching
Hang Hu, Zhao Song, Runzhou Tao +3
Online bipartite matching is a fundamental problem in online algorithms. The goal is to match two sets of vertices to maximize the sum of the edge weights, where for one set of ver…
Edge-Weighted Online Bipartite Matching
Matthew Fahrbach, Zhiyi Huang, Runzhou Tao +1
Online bipartite matching and its variants are among the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) introduced an elega…
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang +3
Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive on…