Minimizing Makespan in Sublinear Time via Weighted Random Sampling

Bin Fu, Yumei Huo, Hairong Zhao · 2026

Read Minimizing Makespan in Sublinear Time via Weighted Random Sampling by Bin Fu, Yumei Huo, Hairong Zhao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04059.txt.

Description

Scheduling jobs on identical machines to finish earliest is a classic hard problem. Bin Fu and 2 co-authors approximate it in sublinear time by sampling. Their 2026 paper gives two schemes for the makespan problem that never read the whole input.

Weighted random sampling picks a representative subset of jobs. One algorithm works when the job count is known, sampling once. The other adapts over several rounds when it is not. Both deliver schedules within a small factor of optimal plus a sketch schedule summarizing the rest. Sublinear methods suit scheduling at platform scale, where even listing every job is too slow.

Catalog record

CREATORBin Fu, Yumei Huo, Hairong Zhao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-04059

Browse the full library · About the Tower of Babel