A. Y. Shavit

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

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...