44 citations · 199 across the 31 of their papers we have counts for
5 papers · 1 filter
Beating One Half for Online Bipartite Matching with Reusable Resources
Xiaohui Bei, Zhihao Gavin Tang, Wenhao Wu
We study online bipartite matching with unit-inventory reusable resources, where requests arrive in an adversarially fixed order, and each use of a resource makes it unavailable fo…
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
Xiaohui Bei, Xiaoming Sun, Hao Wu +3
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness c…
From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
Xiaohui Bei, Shiteng Chen, Ji Guan +2
In the 1970's, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and…
Networked Fairness in Cake Cutting
Xiaohui Bei, Youming Qiao, Shengyu Zhang
We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical f…
Solving Linear Programming with Constraints Unknown
Xiaohui Bei, Ning Chen, Shengyu Zhang
What is the value of input information in solving linear programming? The celebrated ellipsoid algorithm tells us that the full information of input constraints is not necessary; t…