Reproduce “Tight bounds for fractional and randomized truthful scheduling” 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
Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
The authors study truthful scheduling of jobs on machines with private processing times, minimizing the largest machine load. Using linked task families and truthfulness constraints, they prove that every deterministic truthful fractional mechanism has worst-case approximation at least (n + 1)/2, even against the optimal integral makespan. The same bound holds in expectation; a randomized upper bound has an additive term, so the exact ratio remains unsettled.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.