Polytope Scheduling with Groups: Unified Models and Optimal Guarantees

Alexander Lindermayr, Zhenwei Liu, Nicole Megow

TL;DR

This paper introduces a unified mathematical framework called Polytope Scheduling with Groups (PSP-G) that elegantly unifies diverse scheduling and graph coloring problems under a single umbrella. By modeling objectives based on group completion times, the authors deliver a best-possible $\mathcal{O}(\log g)$-competitive algorithm for the online, non-clairvoyant setting (an exponential improvement for coflow scheduling) alongside several improved offline approximation guarantees.

What Problem Does This Paper Address?

In traditional scheduling, algorithms typically aim to minimize either the maximum completion time (makespan) or the average completion time of individual jobs. However, modern applications—such as data center networking (coflow scheduling), data migration, and graph multicoloring—require a more generalized objective: group completion times. Here, a group of entities (jobs, vertices, or edges) only counts as "complete" when the last member of that group finishes.

Historically, these problems were studied in isolation, leading to fragmented techniques and disparate algorithmic bounds. This paper tackles two major challenges:

  1. Lack of Unification: Can we design a single abstract model that captures all these varied group-scheduling problems?
  2. Information and Computational Limits: How well can we schedule these groups when we don't know the job processing times in advance (online non-clairvoyant setting), or when we have full information but face NP-hard computational limits (offline setting)?

Methods

The authors introduce two abstract formulations based on packing polytopes:

  • PSP-G (Continuous): Models preemptive environments where jobs can receive fractional processing rates over time.
  • DPSP-G (Discrete): Models non-preemptive environments or consecutive colorings.

Online Non-Clairvoyant Framework

To solve the online problem where job sizes are unknown until completion, the authors adapt the Proportional Fairness (PF) allocation rule from economics. Standard PF maximizes $\sum w_j \log y_j(t)$ over job rates $y_j(t)$, but it doesn't account for groups. The authors overcome this by introducing virtual weights: each active group distributes its weight evenly among its remaining unfinished jobs. The performance is analyzed using a novel factor-revealing linear program (LP) combined with KKT optimality conditions.

Offline Frameworks

For offline settings, the authors develop two meta-frameworks:

  1. For DPSP-G: An algorithmic framework that reduces the group completion time objective to a simpler makespan minimization problem using interval-indexed LP relaxations and job batching.
  2. For PSP-G: A randomized $(2+\epsilon)$-approximation algorithm that solves a time-indexed LP relaxation, then randomly stretches and truncates the resulting schedule.

Datasets

Not discussed in the paper. This is a purely theoretical paper evaluated using rigorous mathematical proofs and worst-case competitive/approximation ratio analysis rather than empirical datasets.

Key Insights and Ideas

  • The Virtual Weight Trick: Simply applying Proportional Fairness to groups doesn't work because fairness is inherently an individual metric. Evenly dividing a group's weight among its active jobs acts as a perfect proxy, naturally forcing the algorithm to prioritize groups that are close to finishing.
  • Generalizing Queyranne’s Constraints: For the offline discrete framework, the authors show that their time-indexed LP implies a generalization of Queyranne’s classic subset constraints for single-machine scheduling. This allows them to bound the makespan of job batches using an abstract lower bound valid for any downward-closed polytope.

Key Results

The paper provides significant improvements over prior state-of-the-art bounds across multiple domains, as summarized in Table 1:

Table 1: An overview of our new and improved results in comparison to previous work.
  • Online Non-Clairvoyant Coflow Scheduling: Achieves an $\mathcal{O}(\log g)$ competitive ratio, where $g$ is the maximum group size. This exponentially improves upon the previous best bound of $\mathcal{O}(g)$ from BNV20.
  • Offline Related Machines ($Q | r_j | \sum w_S C_S$): Improves the approximation ratio from 13.5 down to 10.874.
  • Sum Multicoloring on Perfect Graphs: Halves the approximation ratio from 10.874 down to 5.437.
  • Preemptive Unrelated Machines ($R | r_j, pmtn | \sum w_S C_S$): Improves the approximation ratio from $4+\epsilon$ to $2+\epsilon$, which is theoretically best-possible under the Unique Games Conjecture.

Limitations and Future Work

  • Dependence on Subroutines: The discrete offline framework (DPSP-G) relies on problem-specific makespan minimization subroutines to achieve its bounds. The authors note it remains an open question whether a fully unified offline discrete algorithm can be designed without relying on these problem-specific properties.
  • Preemptive Offline Gap: For offline PSP-G, the authors achieve a $(2+\epsilon)$-approximation, but it remains open whether this can be improved further for special cases that do not map to the hardest instances of the problem.

Summary updated

Abstract

We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems where the objective function is the weighted sum of completion times over groups of entities (jobs, vertices, or edges), thereby generalizing two important objectives in scheduling: makespan and the sum of weighted completion times. As one of our main results, we present a best-possible $\mathcal O(\log g)$-competitive algorithm in the non-clairvoyant online setting, where $g$ denotes the size of the largest group. This is the first non-trivial competitive bound for several problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. For offline scheduling, we provide elegant yet powerful meta-frameworks that, in a unifying way, yield new or stronger approximation algorithms for our new abstract problems as well as for previously well-studied special cases.
BibTeX
@misc{lindermayr2025polytope,
  author = {Alexander Lindermayr and Zhenwei Liu and Nicole Megow},
  title = {{Polytope Scheduling with Groups: Unified Models and Optimal Guarantees}},
  year = {2025},
  eprint = {2501.17682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.17682},
}
Figure