4 papers
Distributed Load Balancing on Unrelated Machines
Aaron Bernstein, Anupam Gupta, Zhaozi Wang
We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job specifies a size $s_{…
FrontierCS: Evolving Challenges for Evolving Intelligence
Qiuyang Mang, Wenhao Chai, Zhifei Li +48
We introduce FrontierCS, a benchmark of 156 open-ended problems across diverse areas of computer science, designed and reviewed by experts, including CS PhDs and top-tier competiti…
Online Makespan Minimization: Beat LPT by Dynamic Locking
Zhaozi Wang, Zhiwei Ying, Yuhao Zhang
Online makespan minimization is a fundamental problem in scheduling. In this paper, we investigate its over-time formulation, where each job has a release time and a processing tim…
The Long Arm of Nashian Allocation in Online -Mean Welfare Maximization
Zhiyi Huang, Chui Shan Lee, Xinkai Shu +1
We study the online allocation of divisible items to agents with additive valuations for -mean welfare maximization, a problem introduced by Barman, Khan, and Maiti~(2022).…