← 研踪 PaperTrailarXiv:2610.32545 · v2
Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling
首次提交 2026-10-23 20:23
版本更新 2026-10-26 17:45
雷达观测 2026-10-29 00:36
摘要
The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.
作者备注：Shortened abstract
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-26 17:45 · 最新观测版本
Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling
The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.
查看此版本解读 →查看此版本原文 ↗