Papers for

system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Limits found on fair job scheduling methods for unrelated machines

Universally truthful mechanisms for scheduling

Abstract: We consider universally truthful randomized mechanisms for the problem of scheduling $m$ jobs on $n$ unrelated machines. We prove a lower bound on the expected approximation ratio of every such mechanism whose probability distribution has discrete support. We show that no universally truthful randomized mechanism in this class can achieve approximation ratio smaller than $n/12 - o(n)$ with respect to the optimal makespan. We match this, up to a constant factor, by a mechanism with approximation ratio $n/2 + o(n)$.

Fri 11 SeptComputer Science and Game Theory

The gist

Scheduling many jobs on different machines that work in unrelated ways is a tricky problem. The authors studied a special kind of scheduling method that is always truthful in a randomized way, meaning machines have no incentive to lie about their speed. They found a mathematical limit showing these methods can’t schedule jobs too efficiently compared to the best possible solution. They also gave a method that nearly matches this limit, showing the bound is close to the best we can do.

Open → 2609.12621v1