2 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…