4 papers
Harmonic Ranking for Edge-Weighted Oblivious Matching
Bo Peng, Zhihao Gavin Tang
We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe…
Random-Order Online Facility Location Beyond Uniform Opening Costs
Bo Peng, Zhihao Gavin Tang
We study online metric facility location in the random-order model with arbitrary positive opening costs. A finite set of candidate facilities and their costs is known in advance,…
Personalized Clustering via Targeted Representation Learning
Xiwen Geng, Suyun Zhao, Yixin Yu +5
Clustering traditionally aims to reveal a natural grouping structure within unlabeled data. However, this structure may not always align with users' preferences. In this paper, we…
Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
Bo Peng, Zhihao Gavin Tang
We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be -co…