AFTD Auto-Formalizing Theoretical Domains

IsCompetitiveRatio

def

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

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
See it in the graphDiscuss this resultChallenge it