3 papers
cs.GT2026
Randomized Online Fair Division: High-Probability and Expected Realized Fairness
Tianqi Chen, Jingxiao Long
We study randomized algorithms for the fully online allocation of indivisible goods among agents with nonnegative additive valuations. Goods arrive sequentially and must be…
cs.GT2026
Competitive Analysis for Online Fair Division under Multiple Fairness Notions
Tianqi Chen, Zhiyi Tan
We study the online fair division of indivisible items with additive utilities, where items arrive sequentially and must be irrevocably allocated upon arrival. Considering various…
cs.DS2025
Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
Tianqi Chen, Zhiyi Tan
This paper investigates the non-clairvoyant parallel machine scheduling problem with prediction, with the objective of minimizing the makespan. Improved lower bounds for the proble…