7 papers · 1 filter
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,…
Optimal Competitive Ratio of Two-sided Online Bipartite Matching
Zhihao Gavin Tang
We establish an optimal upper bound (negative result) of on the competitive ratio of the fractional version of online bipartite matching with two-sided vertex arrivals…
Combinatorial Philosopher Inequalities
Enze Sun, Zhihao Gavin Tang, Yifan Wang
In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent's valua…
Online Stochastic Matching with Unknown Arrival Order: Beating against the Online Optimum
Enze Sun, Zhihao Gavin Tang, Yifan Wang
We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal -competitive algorithm. A recent li…
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…