CONCEPT Cited by 1 source

Competitive ratio¶

Competitive ratio is the canonical quality metric for an online algorithm: "the worst case comparison between the throughput of our online algorithm and the throughput of an optimal algorithm that is aware of all the jobs apriori" (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

Where an online algorithm must commit decisions as input arrives, the offline baseline sees the whole input in advance and picks the provably optimal response. The competitive ratio ρ = OUT_online / OUT_offline (for throughput-maximisation) is evaluated under an adversarial input — the sequence designed specifically to make the online algorithm underperform — and bounds the algorithm's worst-case performance regardless of which particular sequence actually arrives in production.

Why it matters for schedulers¶

A cluster scheduler only sees the job queue; it doesn't know what workloads will be submitted over the next hour. Worst-case competitive-ratio bounds let the operator reason about what can go wrong without enumerating adversarial inputs:

Ratio 1: online matches offline — no adversary can hurt it.
Constant-competitive (e.g. ½): the online algorithm never does worse than a fixed factor below the optimum, no matter what arrives.
Ratio approaching zero: for long enough inputs, the online algorithm can underperform the optimum arbitrarily — unbounded worst-case loss. This is the regime where the scheduler cannot give any guarantees.

Three preemption regimes for online throughput scheduling¶

Google Research's 2026-02-11 scheduling-under-time-varying- capacity paper reports sharply separated competitive-ratio landscapes across three preemption policies (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity):

No preemption: competitive ratio approaches zero. "A single bad decision of scheduling a long job can ruin the possibility of scheduling many future smaller jobs" — the adversary submits one long job first, the scheduler must commit, a burst of shorts arrives, and throughput is arbitrarily far below optimum.
Interrupt with restart: competitive ratio ½ (matches offline) via the schedule-the-job- that-finishes-earliest greedy. "The flexibility provided by allowing job restarts is highly beneficial" — the ability to walk back a bad commitment is what closes the gap to the offline optimum.
Interrupt without restart (general case): competitive ratio approaches zero again. Losing partial work and losing the job entirely gives the adversary too much leverage.
Interrupt without restart + [[concepts/common-deadline- scheduling|common deadline]]: "novel constant competitive algorithms" — the adversarial lower bound is lifted by restricting the deadline structure.

Typical uses¶

Competitive-ratio analysis is the standard tool for characterising:

Online scheduling — Google Research 2026-02-11 (this source) + foundational theory literature (see concept page).
Online bin-packing — pack items into bins without knowing future items. First-Fit is ~1.7-competitive; this is the regime of cluster VM allocation (2025-10-17 Google LAVA), though the 2025-10-17 post focuses on ML-based policy design rather than competitive-ratio bounds.
Paging and caching — LRU is k-competitive where k is the cache size.
Ski-rental — the canonical 2-competitive toy problem for online decision-making under uncertainty.
Online matching — bipartite matching under arrival of one side; classic 1 − 1/e bound.

Adversarial vs stochastic analysis¶

Competitive-ratio analysis is adversarial (worst-case over all inputs). An alternative is stochastic analysis — average performance over a distribution of inputs — which can give better expected ratios but weaker worst-case guarantees. Production schedulers typically care about both: the adversary model gives robustness claims; stochastic analysis gives the average-case numbers operators actually experience.

The 2026-02-11 post uses adversarial competitive-ratio analysis — the zero-competitive lower bounds are adversarial lower bounds, meaning some input exists that forces arbitrary loss, not that typical inputs do. Production context usually never hits the adversarial input; the point of the analysis is to characterise what can happen, which is load-bearing for scheduler SLA reasoning.

Seen in¶

sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity — competitive-ratio analysis across three preemption regimes for online throughput-maximising scheduling under time-varying capacity; introduces the zero-competitive lower bound for non-preemptive + interrupt-without-restart (general) and the ½-competitive matching upper bound for interrupt-with-restart + constant-competitive bound for interrupt-without-restart under [[concepts/common-deadline- scheduling|common deadlines]].