PaperlayerView exact revision on arXiv

Source-linked AI summary

Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling

Sven Jäger, Alexander Lindermayr, Bart Zondervan

arXiv:2610.32545v2cs.DS

TL;DR

The paper asks whether heterogeneous scheduling environments are intrinsically harder than a single machine under nonclairvoyance. It characterizes support submodularity through concavity of optimal weighted completion time and analyzes Proportional Fairness (PF) using that structure, alongside a dual-fitting analysis for general PSP. PF retains strong completion- and flow-time guarantees on support-submodular polytopes, while general PSP admits a lower bound above 2 for completion time.

  • Problem

    It was open whether PF could achieve the single-machine completion-time factor of 2 on broader PSP classes and which polytopes admit O(1)-speed O(1)-competitive algorithms, particularly given doubts about PF on unrelated machines.

    Source: §1 · p. 3

  • Method

    The paper characterizes support submodularity through concavity of optimal weighted completion time and uses this structure to analyze PF, with dual fitting for general PSP.

    Source: §8 · p. 49

  • Results

    2-competitive for weighted completion time on support-submodular PSP; (2 + ε)-speed O(1/ε)-competitive for weighted flow time there; and at least 2 + 10^-5 for every randomized nonclairvoyant algorithm on general PSP completion time.

    Source: §8 · p. 49

  • Takeaways & Limitations

    Unrelated machines admit the same nonclairvoyant weighted-completion-time guarantee as a single machine, while general PSP is strictly harder for that objective.

    Source: §8 · p. 49

    The concavity-based approach does not yield a constant-factor guarantee for general PSP because the optimal-value function need not have a constant-factor concave approximation.

    Source: §2.4 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether heterogeneous scheduling environments are intrinsically harder than a single machine under nonclairvoyance, and presents support submodularity as a structural route to stronger guarantees. It also contrasts these results with limits for general PSP and situates the work among prior scheduling results.

1.2 Further Related Work

  • Before this work, the best weighted-completion-time ratios were 27 for PSP, 4 for polymatroids, and 3.62 for unrelated machines; without speed augmentation, no nonclairvoyant algorithm is O(1)-competitive for weighted flow time.The introduction also describes prior flow-time guarantees for polymatroids and other scheduling subclasses.Source: §1 · p. 3

1.1 Our Results

  • Support submodularity is equivalent to concavity of optimal weighted completion time for every positive weight vector, and PF is 2-competitive for weighted completion time with uniform release dates on this class.The class includes unrelated machines and polymatroids; the ratio is optimal for nonclairvoyant algorithms under uniform release dates.Source: §1.1 · p. 4
  • The results imply that unrelated machines and a single machine have the same nonclairvoyant completion-time guarantee, and PF's polynomial-time (2 + ε)-approximation matches the best known offline approximation ratio for weighted completion time in PSP.With arbitrary release dates, PF's ratio of 3 matches the best known guarantee for deterministic clairvoyant online algorithms on unrelated machines.Source: §1.1 · p. 4
  • With (2 + ε)-speed, PF is O(1/ε)-competitive for weighted flow time on support-submodular PSP, including unrelated machines and polymatroids.The class also includes generalized flow scheduling and RS-S with separable utilities; the guarantee improves on prior bounds for the intersection with PF-monotone polytopes.Source: §1.1 · pp. 4–5
  • Every randomized nonclairvoyant algorithm has ratio at least 2 + 10^-5 for total completion time in PSP, even for graph scheduling with uniform release dates.The authors present this as the first PSP lower bound strictly above the single-machine lower bound of 2.Source: §1.1 · p. 5
  • For weighted completion time in general PSP, PF is 4-competitive with arbitrary release dates, using a new dual-fitting analysis.The prior guarantee was 27; the concavity-based route does not give a constant-factor guarantee for general PSP.Source: §1.1 · p. 6
  • PF is (4 + ε)-speed O(1/ε)-competitive for weighted flow time in graph scheduling, although graph scheduling is generally neither support submodular nor PF-monotone.The result is a special case of a guarantee for downward-closed polytopes between a binary packing polytope with at most c ones per column and its integer hull.Source: §1.1 · p. 6

1.3 Paper Organization

  • The introduction reviews related results on support-function submodularity and organizes the paper around techniques, preliminaries, structural proofs, and general-PSP results.It states that Sections 2–7 cover these topics and proofs.Source: §1.2 · p. 6, §1.3 · p. 7

2 Technical Overview

This section connects Proportional Fairness guarantees to rate-polytope geometry, explaining how support submodularity characterizes concavity of optimal weighted completion time. For general PSP, it presents a randomized lower bound and a dual-fitting analysis that bounds PF via a per-job construction balancing processing against lost credit.

2.1.1 Reduction to Concavity

  • PF is 2-competitive whenever optimal weighted completion time is concave in processing requirements.The reduction uses positive homogeneity, which makes concavity equivalent to superadditivity, together with a pointwise bound from PF’s first-order optimality conditions.Source: §2.1 · p. 8, §2.1.1 · p. 8

2.1.2 Warm-up: A Single Machine

  • For support-submodular polytopes, optimal weighted completion time is a minimum of finitely many linear functions; the same representation holds for nonpreemptive unrelated-machine schedules [BCS74; Hor73].On a single machine, each job order gives one linear function of processing requirements.Source: §2.1.2 · pp. 8–9

2.1.3 Fixed-Order Bounds

  • Backward-constructed prices make every suffix of a completion order tight, yielding fixed-order bounds whose minimum equals optimal weighted completion time.The lower bound holds for every rate polytope; support submodularity is needed for the matching upper bound.Source: §2.1.3 · pp. 9–10

2.1.4 Greedy Schedules and Support Submodularity

  • Support submodularity extends the tight-suffix price inequalities to all job sets, so the corresponding greedy schedule gives an upper bound on optimal weighted completion time.The greedy schedule processes jobs at rates maximizing the price-weighted rate over the unfinished jobs.Source: §2.1.4 · p. 10

2.1.5 Completing the Proofs

  • For all positive weight vectors, support submodularity is equivalent to concavity of optimal weighted completion time, and a minimizing order’s greedy schedule is optimal.Concavity for only one weight vector does not imply support submodularity.Source: §2.1.5 · pp. 10–11

2.2 Weighted Flow Time for Support-Submodular PSP and Beyond

  • For graph scheduling, PF is (4 + ε)-speed O(1/ε)-competitive; c-approximate certificates yield (2c + ε)-speed O(c/ε)-competitiveness.The analysis uses a potential based on optimal weighted completion time for the lag instance, with price vectors serving as supergradients.Source: §2.2 · pp. 11–12

2.3 A Randomized Lower Bound for General PSP

  • 10/(5 − 9·10^-5) > 2 + 10^-5: Yao’s principle gives this lower bound for every randomized nonclairvoyant algorithm on general PSP.The construction uses graph scheduling on a four-vertex path with three groups of parallel unit-weight jobs.Source: §2.3 · p. 12

2.4 Dual Fitting for General PSP

  • A constructed feasible dual solution has value at least PF/4, and weak duality places every feasible dual value at most OPT, yielding PF ≤ 4OPT.Source: §2.4 · p. 13
  • A job loses credit only when its normalized processing rate exceeds 1/(4t), and it receives only pj units of processing through completion.The analysis uses the tradeoff between processing accumulated and credit lost to show that each job keeps at least half its credit.Source: §2.4 · p. 14
  • The fitted dual has value at least PF/4, proving Theorem 1.6.Each job retains at least half its credit, so summing job credits yields at least PF/2; after subtracting PF/4, the fitted dual is worth at least PF/4.Source: §2.4 · p. 14
  • Earlier global-quantile dual fitting gives factor 27, whereas PF’s per-job credits fit the unit-capacity dual directly and avoid the capacity loss.The earlier approach uses λ = 2/3 and κ = 9; the new construction derives each job’s credit from its own normalized rate and discounts PF’s KKT prices by 1/(4t).Source: §2.4 · p. 14

3 Preliminaries

PSP models preemptive scheduling as allocating job-processing rates from a feasible polytope over time. PF allocates rates among active jobs using their weights and the rate polytope, without knowing processing requirements.

3.1 Polytope Scheduling

  • A PSP schedule assigns each job a processing rate over time, subject to instantaneous polytope constraints and enough cumulative processing to complete each job.The model includes job weights, processing requirements, and release dates; speed augmentation scales the processing accumulated by a schedule.Source: §3.1 · pp. 14–15
  • Online algorithms learn each job’s weight and rate-polytope column at release, while nonclairvoyant algorithms learn its processing requirement only when it completes.An online algorithm fixes rates using only jobs released so far and cannot revise those decisions later.Source: §3.1 · p. 15

3.2 Proportional Fairness

  • PF solves an Eisenberg–Gale convex program for active jobs and uses only their weights and rate-polytope columns, never their processing requirements.It recomputes rates when a job is released or completes; approximate solutions suffice for the stated guarantees up to a factor of 1 + ε.Source: §3.2 · p. 16

4 Support-Submodular PSP

This section defines support-submodular polytopes through submodularity of restricted support values and identifies scheduling models that satisfy or fail this property. It also explains how support submodularity enables PF to retain single-machine guarantees in separable-utility scheduling with substitutes, while complementarity can prevent it in graph scheduling.

4 Support-Submodular PSP

  • Support-submodular polytopes include polymatroid, unrelated-machine, generalized-flow, and concave-speedup scheduling, while graph, multicommodity-flow, and all-or-nothing scheduling are not support submodular in general.The class is defined by submodularity of the set function of maximum achievable value on each job subset, for every nonnegative direction.Source: §4 · p. 17, §4.1 · p. 18

4.1 The Support Function and Submodularity

  • A PSP polytope is support submodular when, for every nonnegative α, its restricted support values form a submodular set function over job subsets.The condition depends on the polytope alone, not on job weights or processing requirements.Source: §4.1 · p. 18

4.2 Polymatroids and Generalized Flow Scheduling

  • Polymatroids and generalized-flow rate polytopes satisfy the lattice-submodularity condition and are support submodular and PF-monotone for all positive job weights.The framework does not extend in general to multicommodity flow scheduling, where each job routes its own commodity.Source: §4.2 · pp. 18, 20, 21

4.3 Unrelated Machine Scheduling

  • Unrelated-machine scheduling with preemption and migration is support submodular, although its support function need not be submodular on the whole nonnegative lattice.For each α, the restricted support value is a maximum-weight matching value on machines and the selected job set, which has diminishing returns.Source: §4.3 · p. 22

4.4 Multidimensional Resource Scheduling with Substitutes

  • For resource scheduling with substitutes and separable utilities, the support function satisfies the lattice-submodularity condition; piecewise-linear cases reduce to generalized flow, and general utilities follow by approximation.This includes scheduling with concave speedup curves.Source: §4.4 · p. 24
  • Every RS-S instance with separable utilities is support submodular, and its rate body admits support-submodular polytope approximations Pε with (1 − ε)P ⊆ Pε ⊆ P.The approximation applies even when the feasible rate body is not itself a polytope.Source: §4.4 · p. 25
  • 2-competitive for weighted completion time with all jobs released at time 0, and for every κ > 2, PF with speed κ is κ/(κ−2)-competitive for weighted flow time with arbitrary release dates.These guarantees hold for RS-S instances with separable utilities.Source: §4.4 · p. 25

4.5 Non-Support-Submodular Scheduling Problems

  • A graph-scheduling rate polytope is support submodular exactly when every connected component is a star or triangle, equivalently when the instance is a collection of independent single machines.Graph-scheduling allocations are matchings, so their feasible rate body is the matching polytope.Source: §4.5 · pp. 26–27
  • Complementarity obstructs support submodularity: a graph-scheduling job can block two noncompeting jobs, making one blocked job's marginal value rise when the other is present.Graph scheduling, multicommodity flow scheduling, all-or-nothing scheduling, and RS-S with nonseparable utilities are not support submodular in general.Source: §4.5 · pp. 26–27

5 Weighted Completion Time for Support-Submodular PSP

This section completes the proof of Theorem 1.2 by establishing the equivalence between support submodularity and concavity of optimal weighted completion time in processing requirements, and showing how that concavity yields PF’s guarantees. It also shows that concavity for a single weight vector alone does not imply support submodularity.

5.1 Fixed-Order Bounds

  • For every order π, a unique price vector απ with tight suffixes gives the fixed-order lower bound ⟨απ,p⟩ ≤ OPTπ(p).The price vector depends on the order, weights, and rate polytope, not on processing requirements.Source: §5.1 · p. 28

5.2 Greedy Schedules and Concavity

  • For support-submodular PSP, OPT(p) equals the minimum over orders π of ⟨απ,p⟩, and an απ-greedy schedule is optimal for every minimizing order.The vectors απ are independent of p, so OPT(p) is concave as a minimum of finitely many linear functions.Source: §5.2 · p. 30

5.3 Proof of Theorem 1.3

  • PF is 2-competitive for weighted completion time with uniform release dates and 3-competitive with arbitrary release dates.The arbitrary-release guarantee is for support-submodular PSP.Source: §5.3 · p. 31

5.4 Concavity for All Weights Implies Support Submodularity

  • For every positive weight vector, concavity of p ↦ OPT(p) implies that the downward-closed rate polytope is support submodular.The proof constructs processing vectors whose optimal costs violate concavity if support submodularity fails.Source: §5.4 · pp. 32–33
  • Together with Theorem 5.6, this proof establishes Theorem 1.2.The section concludes its proof by combining the result established here with Theorem 5.6.Source: §5.4 · p. 35
  • For the triangle fractional matching polytope, unit-weight OPT is concave although the polytope is not support submodular.The proposition shows that concavity for one weight vector is insufficient to imply support submodularity.Source: §5.4 · p. 35
  • With α=1, Hα({1,2})=Hα({1,3})=Hα({1})=1, while Hα({1,2,3})=3/2, witnessing non-submodularity.For concavity, the proof directly verifies the inequalities used in the earlier argument and expresses OPT as a minimum of linear functions.Source: §5.4 · p. 35

6 Weighted Flow Time for Support-Submodular PSP and Beyond

The section extends PF’s weighted-flow-time guarantees from support-submodular polytopes to polytopes admitting approximate certificates. It applies this extension to sparse binary packing constraints, including graph scheduling.

6 Weighted Flow Time for Support-Submodular PSP and Beyond

  • For every ε > 0, PF is (2c + ε)-speed O(c/ε)-competitive for weighted flow time on polytopes admitting a c-approximate certificate.The general guarantee applies for speed augmentation κ > 2c, with competitive ratio κ/(κ−2c).Source: §6 · p. 36

6.1 Potential Function

  • A potential evaluates the certificate-based cost of PF’s lag behind a unit-speed comparison schedule, and its derivative is bounded before integration.The proof compares PF with an arbitrary feasible schedule and bounds the potential’s derivative using certificate prices and PF’s allocation optimality.Source: §6.1 · pp. 36–37

6 Weighted Flow Time for Support-Submodular PSP and Beyond

  • PF is (2 + ε)-speed O(1/ε)-competitive for weighted flow time on support-submodular polytopes.This follows by assigning each processing vector an optimal-order certificate with approximation factor 1.Source: §6 · p. 35, §6.1 · p. 38

6.2 Application: Sparse Binary Packing Constraints

  • Every downward-closed polytope between a c-sparse binary polytope’s integer hull and the polytope admits a c-approximate certificate for all weights.Here each column of the binary constraint matrix has between one and c ones.Source: §6.2 · p. 39
  • The sparse-binary certificate relaxes scheduling into independent single-machine problems, which one global Smith order solves simultaneously.Column sparsity controls how often a job is charged across the relaxed resource subproblems.Source: §6.2 · p. 39
  • For graph scheduling, PF is (4 + ε)-speed O(1/ε)-competitive for weighted flow time.This is the c = 2 application of the sparse binary packing result.Source: §6.2 · pp. 39, 41

7 Weighted Completion Time for General PSP

The section studies weighted completion time for general polytope scheduling, including arbitrary release dates. It establishes a randomized nonclairvoyant lower bound above 2 for total completion time and proves that Proportional Fairness is 4-competitive for weighted completion time.

7.1 A Randomized Lower Bound for General PSP

  • Theorem 1.5 establishes that every randomized nonclairvoyant algorithm for total completion time in PSP has competitive ratio at least 2 + 10−5, even for graph scheduling with uniform release dates.Source: §7.1 · p. 42

7.2 Dual Fitting for General PSP

  • PF is 4-competitive for weighted completion time in PSP with arbitrary release dates, improving the previous known ratio of 27.The analysis directly fits a dual solution to PF, discounting each job’s credit according to its own normalized rate rather than a global quantile.Source: §7.2 · pp. 45–46

7.2.1 A Continuous-Time Relaxation

  • The continuous-time mean-busy-time relaxation lower-bounds the optimal weighted completion time, and every feasible dual solution lower-bounds the relaxation.The relaxation charges each job its mean busy time instead of its completion time.Source: §7.2.1 · p. 46

7.2.2 Fitting a Dual Solution to Proportional Fairness

  • The PF-fitted dual assigns each job a discounted version of its PF cost and sets resource prices by aggregating PF’s future resource prices.A parameterized integral bound relates the dual objective to PF, yielding the 4-competitive guarantee.Source: §7.2.2 · pp. 47–48
  • PF is 4-competitive on general polytopes with arbitrary release dates.The dual-fitting analysis bounds PF by 4·OPT using a function whose maximum is 1/4 at θ = 1/4.Source: §7.2.2 · p. 49

8 Conclusion

PF matches the single-machine weighted-completion-time guarantee on support-submodular PSP, and the class includes unrelated machines. For general PSP, the paper improves PF’s completion-time guarantee while establishing a lower bound above 2, and gives new weighted-flow-time guarantees for support-submodular and graph scheduling.

8 Conclusion

  • 2-competitive PF for weighted completion time on support-submodular PSP is optimal for nonclairvoyant algorithms, even though the class includes unrelated machines.The optimality comparison is with the single-machine lower bound.Source: §8 · p. 49
  • 3-competitive PF for weighted completion time on support-submodular PSP with arbitrary release dates is not optimal; 2-competitive nonclairvoyant algorithms exist on a single machine.PF is not better than 2.19-competitive even on a single machine in this setting.Source: §8 · p. 49
  • 4 is PF’s competitive ratio for weighted completion time on general PSP, while every randomized nonclairvoyant algorithm has ratio at least 2 + 10^-5, even with unit weights and uniform releases.The upper bound improves PF’s previous ratio of 27.Source: §8 · p. 49
  • PF with (2 + ε)-speed is O(1/ε)-competitive for weighted flow time on support-submodular PSP, including unrelated machines.The paper states that this is tight for PF and improves the previous guarantee on the intersection with PF-monotone PSP.Source: §8 · p. 49
  • For graph scheduling, PF with (4 + ε)-speed is O(1/ε)-competitive, giving the first O(1)-speed O(1)-competitive nonclairvoyant algorithm.The paper also gives a broader guarantee for downward-closed polytopes between binary packing polytopes of column sparsity at most c and their integer hulls.Source: §8 · p. 49

A Comparison with CIP25

The comparison distinguishes the conditions and potential functions used by Chen, Im, and Petety [CIP25] from those in this paper. The paper’s approach uses lag relative to a fixed feasible schedule and does not require PF to compute a residual optimum.

A Comparison with CIP25

  • Chen, Im, and Petety [CIP25] obtain scalable clairvoyant algorithms by gradient descent on the residual optimum and assume supermodularity of that optimum or a substitutes condition.The two assumptions are stated respectively in [CIP25, Theorem 3.2] and [CIP25, Theorem 3.3].Source: A Comparison with CIP25 · p. 50
  • A linear-substitute valuation for every nonnegative c implies support submodularity and PF-monotonicity for every positive weight vector.The paper states this implication in Proposition A.1.Source: A Comparison with CIP25 · p. 50
  • Support submodularity is strictly weaker than the substitutes hypothesis: unrelated machines are support-submodular but are not generally PF-monotone.Chen, Im, and Petety [CIP25] handle unrelated machines with separate arguments.Source: A Comparison with CIP25 · p. 50
  • The compared potentials differ: [CIP25] combines residual optima, while this paper evaluates OPT0 on PF’s lag from a fixed feasible schedule.The paper says arrivals have zero lag, so they do not change its potential; PF itself never computes a residual optimum.Source: A Comparison with CIP25 · p. 50

B Unbounded Concavity for General PSP

For support-submodular rate polytopes, optimal weighted completion time is concave in processing requirements, a property used in PF’s competitive analysis. The appendix shows that the resulting concavity-based framework cannot give a constant competitive ratio for general PSP.

B Unbounded Concavity for General PSP

  • For support-submodular rate polytopes, OPT(p) is concave, and this is the only polytope property used in the cited PF competitive analysis.The appendix asks whether general PSP admits a concave constant-factor approximation because such an approximation would yield 2c-competitiveness for PF.Source: B Unbounded Concavity for General PSP · pp. 50–51
  • If an instance is c-concave, PF is 2c-competitive for weighted completion time when all jobs are released at time 0.The argument uses the bound OPT ≤ G and the concavity and positive homogeneity of G.Source: B Unbounded Concavity for General PSP · p. 51
  • For every c ≥ 1, there is a unit-weight PSP instance that is not c-concave, ruling out a constant c-concavity guarantee for general PSP.Consequently, the c-concavity framework cannot give PF a constant competitive ratio for general PSP.Source: B Unbounded Concavity for General PSP · p. 51
  • The counterexample uses a complete m-ary rooted tree: vertices are jobs, root-leaf paths define packing constraints, and each vertex’s processing requirement equals the number of paths containing it.The construction decomposes the processing vector into one indicator-vector part for each root-leaf path.Source: B Unbounded Concavity for General PSP · p. 51
  • The proof contrasts costly path-supported parts with a cheaper schedule of whole tree levels, establishing that no constant-factor concave approximation works for all such instances.The path-supported part is a single unit-speed machine with k + 1 unit jobs; the combined instance can process levels in sequence.Source: B Unbounded Concavity for General PSP · pp. 51–52

C Non-Support-Submodular Rate Sets

This section identifies scheduling polytopes that are not support submodular and characterizes graph-scheduling instances that are support submodular. It also shows that the support-submodularity condition for resource scheduling with substitutes is sharp.

C Non-Support-Submodular Rate Sets

  • Multicommodity flow scheduling and all-or-nothing scheduling each contain instances that are not c-concave for every constant c ≥1, and neither problem is support submodular.The section also shows that a single job with ρj < 1 can break support submodularity in resource scheduling with substitutes, although the rate set is support submodular when all ρj = ρ′j = 1.Source: C Non-Support-Submodular Rate Sets · p. 52
  • Graph scheduling is characterized by whether every connected component is a star or a triangle.The section states that this condition is sharp for support submodularity of the matching polytope.Source: C Non-Support-Submodular Rate Sets · p. 52
  • A single job with ρj < 1 can already break support submodularity in resource scheduling with substitutes.The section establishes support submodularity when ρj = ρ′j = 1 for every job.Source: C Non-Support-Submodular Rate Sets · p. 52

C.1 Multicommodity Flow Scheduling

The section models multicommodity flow scheduling through shared arc capacities and constructs an instance realizing a tree polytope. This yields instances that are not c-concave for any constant c ≥1, so the scheduling problem is not support submodular.

C.1 Multicommodity Flow Scheduling

  • Jobs route flow between source–sink pairs, while their rates share arc-capacity constraints.Each job’s rate is the total flow it sends, and each arc constrains all jobs whose flow uses it.Source: §C.1 · p. 52
  • For every constant c ≥1, multicommodity flow scheduling contains a unit-weight instance that is not c-concave, and the problem is not support submodular.The construction realizes the tree instance of Proposition B.2.Source: §C.1 · pp. 52–53
  • A directed path with unit-capacity arcs realizes the tree instance by assigning each tree vertex a commodity using its corresponding subpath.The path is the unique route for each commodity, and the resulting capacity constraints match those of the tree polytope.Source: §C.1 · p. 53

C.2 All-or-Nothing Scheduling

The section represents all-or-nothing scheduling as a downward-closed convex hull of set-incidence vectors. By realizing the tree instance with antichains, it shows that the problem is not support submodular.

C.2 All-or-Nothing Scheduling

  • A chosen set receives a share of one unit of resource and contributes that rate simultaneously to every job in the set.The rate polytope is the downward closure of the convex hull of the origin and the sets’ indicator vectors.Source: §C.2 · p. 53
  • For every constant c ≥1, all-or-nothing scheduling contains a unit-weight instance that is not c-concave, and the problem is not support submodular.The construction realizes the tree instance of Proposition B.2.Source: §C.2 · p. 53
  • Choosing the tree’s antichains as the sets makes the resulting polytope equal to the tree polytope.The proof uses integrality of the interval-matrix polytope and identifies its integral points with antichain incidence vectors.Source: §C.2 · p. 53

C.3 Graph Scheduling

For graph scheduling, the matching polytope is support submodular exactly when every connected component is a star or a triangle. The section connects this characterization to concavity of optimal weighted completion time and gives a three-edge path counterexample.

C.3 Graph Scheduling

  • The matching polytope is support submodular if and only if every connected component is a star or a triangle.The section defines these components so that any two edges in the component share an endpoint.Source: §C.3 · p. 54
  • For graphs with only star or triangle components, the matching polytope equals a partition-matroid polymatroid.Each matching uses at most one edge per component, and edges in different components are disjoint.Source: §C.3 · p. 54
  • A component with two disjoint edges contains a path of at least three edges that witnesses failure of support submodularity.The proof uses overlapping edge sets along the path and matching incidence vectors to construct the violation.Source: §C.3 · p. 54
  • The star-or-triangle condition holds exactly when optimal weighted completion time is concave in processing requirements for every weight vector.This follows by combining the graph characterization with the stated equivalence between support submodularity and concavity.Source: §C.3 · p. 54
  • If a component is neither a star nor a triangle, some weight vector makes the optimal-value function nonconcave.A unit-weight path with three edges already gives a nonconcave example and a matching polytope that is not PF-monotone.Source: §C.3 · p. 55
  • On the unit-weight three-edge path, removing the first edge reduces the third edge’s PF rate from 2/3 to 1/2.The rates are obtained from the proportional-fair solutions before and after removing the edge.Source: §C.3 · p. 55
  • For the same path, OPT(1, 1, 0) + OPT(0, 1, 1) = 6 exceeds OPT(1, 2, 1), which is at most 5.The feasible schedule processes the first and third edges together for one time unit, then the second edge for two time units.Source: §C.3 · p. 55

C.4 RS-S Is Not Support Submodular for ρ < 1

RS-S is support submodular when all parameters equal 1, but this property fails for every ρ in (0, 1). A two-resource, three-job construction witnesses the failure through a strict violation of support-function submodularity.

C.4 RS-S Is Not Support Submodular for ρ < 1

  • For every ρ in (0, 1), an RS-S instance has a feasible rate set that is not support submodular.This contrasts with the stated support-submodularity result when all ρ_j and ρ′_j equal 1.Source: §C.4 · p. 55
  • The witness uses two resources and three jobs: two with separable utilities and one with a CES aggregate parameter ρ < 1.The support-function violation persists after adding small positive terms to make the first two jobs’ utilities increasing.Source: §C.4 · p. 55
  • For the chosen job sets, the construction makes the sum of the two support values strictly less than the union-plus-intersection values.This is the submodularity inequality in the wrong direction for U = {1, 3} and V = {2, 3}.Source: §C.4 · pp. 55–56

D Polynomial-Time Implementation of Proportional Fairness

PF recomputes rates when jobs arrive or complete, and polynomial-time approximate solutions suffice for the stated guarantees up to a factor of 1 + ε. The implementation relies on rational input and an explicit or efficiently separable representation of the rate polytope.

D Polynomial-Time Implementation of Proportional Fairness

  • PF recomputes rates by solving (CP) when a job is released or completes, and polynomial-time approximate solutions suffice for all guarantees up to a factor of 1 + ε.Each job is released and completes once, so PF solves at most 2n instances of (CP).Source: D Polynomial-Time Implementation of… · pp. 56–57
  • The computational claims assume rational input and either an explicit matrix or a well-described rational rate polytope with a polynomial-time separation oracle.The text identifies compact extended formulations for unrelated machines and generalized flow scheduling, and polynomial-time separation for graph scheduling’s matching polytope.Source: D Polynomial-Time Implementation of… · p. 56
  • For each nonempty active set, the ellipsoid method computes feasible rates in polynomial time that are at least the exact rates divided by 1 + ρ.This relative guarantee follows from choosing the coordinatewise approximation tolerance using a lower bound on each exact rate.Source: D Polynomial-Time Implementation of… · p. 57
  • Approximate PF preserves the stated guarantees with controlled ratio changes, including completion-time ratios 2(1 + ρ) and 3 + 2ρ and a weighted-flow ratio κ/[κ − 2c(1 + ρ)].The flow-time bound requires κ > 2c(1 + ρ), with sufficiently small ρ = O(ε/c) preserving the stated bounds.Source: D Polynomial-Time Implementation of… · p. 57

AI Methodology Statement

The authors report using language models during preparation for selected constructions, proof ideas, and an integral evaluation. They state that authors verified the AI-assisted contributions and take responsibility for correctness.

AI Methodology Statement

  • ChatGPT-6 Astra assisted with constructions for Theorems 1.5 and 5.8, while ChatGPT-5.5 gave an initial hint for applying linear certificates to weighted flow time.Source: AI Methodology Statement · p. 57
  • Claude Opus 4.8 assisted with an integral evaluation, and Claude Opus 5.5 helped work out a connection among three stated conditions.The conditions are support submodularity, the condition of, and the substitutes condition of [CIP25].Source: AI Methodology Statement · p. 57
  • The authors say they verified all AI-assisted contributions, take full responsibility for correctness, and used AI otherwise only for minor language editing.Source: AI Methodology Statement · p. 57
Loading 2610.32545v2…