Papers for

scheduling system developers

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.

Wang-Sitters scheduling method limit stays fixed at 11 over 6

Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6

Abstract: The 11/6 worst-case constant of the Wang-Sitters rounding scheme, which a companion note establishes, can naturally be attributed to the freedom in Step 3, where an arbitrary valid slot matching is permitted. We show that eliminating that freedom does not improve the constant. A minimum-makespan completion oracle still has worst-case constant exactly 11/6 against the optimum; both natural 7/4 statements about it are false; and restricting Step 1 to vertices of the relaxation does not help. The loss therefore cannot be attributed solely to the freedom in Step 3. We also record what structure survives: a reduction confining every overload to two shapes, a seven-machine instance defeating the natural two-phase repair, and a strict 7/4 bound on the generalized three-path family.

Wed 9 SeptData Structures and Algorithms

The gist

This paper studies a specific scheduling method called the Wang-Sitters rounding scheme, used to assign tasks to machines efficiently. The authors find that even when restricting certain choices in the method, the worst-case performance ratio remains exactly 11/6 compared to the best possible schedule. They also show that some natural guesses about improving the method's bounds are incorrect. Their analysis highlights which parts of the problem structure are still relevant despite these limits.

Open → 2609.10004v1