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
Data Structures and Algorithms
Summary
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.
What this means in practice
- •For scheduling system developers: Assess the limits of Wang-Sitters based scheduling approximations under constrained assignment rules when optimizing machine workloads.
- •For manufacturing process planners: Understand inherent bounds in task-to-machine assignment methods to guide realistic expectations in complex job scheduling scenarios.
A theory result. No direct application yet.
Authors
Adam Y. Shavit
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.