Reproduce “Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Wenqian Wang, Chenyang Xu, Yuhao Zhang
The authors prove that truthful-in-expectation mechanisms for makespan scheduling on m unrelated machines cannot achieve approximation ratios below (m+1)/2. They convert truthfulness into a limit on how allocations can depend on groups of jobs, then use a star-shaped hard instance to show that this limit forces a large expected makespan. The result is a lower bound; the known upper bound is (m+5)/2.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.