3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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…