IsCompetitiveRatio
A schedule generator Alg is ρ-competitive for cache capacity k and initial cache C₀ if it is online, produces a feasible schedule whenever a feasible offline schedule exists for the request list, and its total fetch cost evaluated at instanceHorizon reqs on every feasible request list is at most ρ times the fetch cost of any feasible offline schedule optSched evaluated at instanceHorizon reqs plus a constant c.
Statement
def IsCompetitiveRatio {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) (ρ : ℝ) : Prop
- Defined in
- arXiv:2610.18767 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 5
- DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
- IsFeasibleScheduleA schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it…
- scheduleCostThe total fetch cost of a cache schedule up to time T, defined as the sum over time steps of the number of newly fetched pages.
- instanceHorizonThe finite time horizon of a list of deadline requests, defined as one more than the maximum deadline, or zero if empty.
- IsOnlineClairvoyantScheduleGenA deterministic clairvoyant online schedule generator on lists of requests produces a cache configuration at time t that depends only on…
- Used by 2
- not_deadline_paging_upper_bound_k_plus_oneThe statement
deadline_paging_upper_bound_k_plus_oneis false: The statement (for every k≥1, every finite α with card ≥ k+1, every C₀ of… - deadline_paging_lower_bound_k_plus_halfFor every cache capacity k ≥ 1, every finite page universe α with at least k + 2 pages, every initial cache C₀ of size k, every schedule…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
Given a type α with decidable equality, a cache capacity k : ℕ, an initial cache configuration C₀ : Finset α, an online scheduling algorithm Alg : List (DeadlineRequest α) → (ℕ → Finset α), and a real number ρ : ℝ, IsCompetitiveRatio k C₀ Alg ρ asserts that:
1. Alg is an online clairvoyant schedule generator: for any two request lists reqs₁ and reqs₂ and any time step t : ℕ, if the sublists of requests with arrival time at most t are identical, then Alg reqs₁ t = Alg reqs₂ t.
2. Feasibility preservation: for every request list reqs, if there exists any feasible schedule opt for reqs (with capacity k and initial cache C₀), then the schedule generated by Alg reqs is also feasible for k, C₀, and reqs.
3. Competitive ratio bound: there exists a real constant c such that for every request list reqs and every schedule optSched : ℕ → Finset α, if optSched is feasible for k, C₀, and reqs, then the cost of Alg reqs up to the instance horizon of reqs is at most ρ times the cost of optSched up to the instance horizon of reqs, plus c.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A deterministic online algorithm is ρ-competitive for paging with deadlines starting from initial cache C₀. -/ def IsCompetitiveRatio {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) (ρ : ℝ) : Prop := IsOnlineClairvoyantScheduleGen Alg ∧ (∀ reqs, (∃ opt, IsFeasibleSchedule k C₀ opt reqs) → IsFeasibleSchedule k C₀ (Alg reqs) reqs) ∧ ∃ c : ℝ, ∀ (reqs : List (DeadlineRequest α)) (optSched : ℕ → Finset α), IsFeasibleSchedule k C₀ optSched reqs → (scheduleCost (Alg reqs) (instanceHorizon reqs) : ℝ) ≤ ρ * (scheduleCost optSched (instanceHorizon reqs) : ℝ) + c