The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling

The polytope scheduling problem (PSP) was introduced by Im, Kulkarni, and Munagala [ J. ACM, 65 (2018), pp. 3:1–3:33] as a very general abstraction of resource allocation over time, where jobs can receive processing rates subject to arbitrary packing constraints. It captures many well-studied problems, including classical unrelated machine scheduling, multidimensional scheduling, and broadcast scheduling. An elegant and well-known algorithm for instantaneous rate allocation with good fairness and efficiency properties is the proportional fairness (PF) algorithm, which was analyzed for PSP by Im, Kulkarni, and Munagala. We drastically improve the analysis of PF for both the general PSP and several of its important special cases subject to the objective of minimizing the sum of weighted completion times. We reduce the upper bound on the competitive ratio from 128 to 27 for general PSP and to 4 for the prominent class of monotone PSP. For certain heterogeneous machine environments, we even close the substantial gap to the lower bound of 2 for nonclairvoyant scheduling. Our analysis also gives the first polynomial-time improvement over the nearly 30-year-old bounds on the competitive ratio of the doubling framework, which was introduced by Hall, Shmoys, and Wein (SODA 1996) for clairvoyant online preemptive scheduling on unrelated machines. Somewhat surprisingly, we achieve this improvement by a nonclairvoyant algorithm, thereby demonstrating that nonclairvoyance is not a (significant) hurdle. Our improvements are based on exploiting monotonicity properties of PSP, providing tight dual fitting arguments on structured instances, and showing new algebraic properties of the optimal objective value for scheduling on unrelated machines. Finally, we establish new connections between PF and matching markets and thereby provide new insights on equilibria and their computational complexity.