deadline_paging_min_cost_schedule_exists
Every feasible deadline-paging instance admits a feasible schedule whose fetch cost over the instance horizon is minimal among all feasible schedules (the offline optimum, made concrete).
Statement
theorem deadline_paging_min_cost_schedule_exists {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (reqs : List (DeadlineRequest α)) (h : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ ∀ sched' : ℕ → Finset α, IsFeasibleSchedule k C₀ sched' reqs → scheduleCost sched (instanceHorizon reqs) ≤ scheduleCost sched' (instanceHorizon reqs)
- Source
- step towards deadline_paging_optimal_competitive_ratio_two_holes
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
The proof, explained
The theorem establishes the existence of a cost-minimizing feasible schedule using the well-ordering principle of the natural numbers. Because a feasible schedule exists by hypothesis, the set of costs achievable by feasible schedules over the instance horizon is a non-empty subset of ℕ. The schedule attaining the minimum element of this set is therefore an optimal feasible schedule.
The set of fetch costs realized by feasible schedules over the horizon is non-empty.
Under classical logic, we extract a witness feasible schedule $s_0$ from the feasibility hypothesis $h$. We define the predicate $P(n)$ stating that $n$ is the horizon schedule cost of some feasible schedule, and witness that $P$ is non-empty using the cost of $s_0$.
classical obtain ⟨s₀, hs₀⟩ := h let P : ℕ → Prop := fun n => ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = n have h_ex : ∃ n, P n := ⟨scheduleCost s₀ (instanceHorizon reqs), s₀, hs₀, rfl⟩
There exists a feasible schedule `sched` achieving the minimal cost `Nat.find h_ex`.
By the well-ordering principle of the natural numbers (`Nat.find_spec`), the non-empty predicate $P$ has a least element $\operatorname{Nat.find}(h\_ex)$. We unpack the specification to obtain a concrete schedule `sched` that is feasible and achieves this minimal cost.
uses
Nat.find_specobtain ⟨sched, hsched_feas, hsched_cost⟩ := Nat.find_spec h_exThe schedule `sched` is feasible and its cost is at most the cost of any feasible schedule `sched'`.
We propose `sched` as the desired schedule and provide its feasibility. For any other feasible schedule `sched'`, we rewrite the cost of `sched` to $\operatorname{Nat.find}(h\_ex)$, and conclude using `Nat.find_min'` since `sched'` demonstrates that its own cost satisfies $P$.
uses
Nat.find_min'refine ⟨sched, hsched_feas, fun sched' hsched' => ?_⟩ rw [hsched_cost] exact Nat.find_min' h_ex ⟨sched', hsched', rfl⟩
Nat.find_spec- If a predicate on natural numbers is satisfied by some natural number, then `Nat.find` produces a witness that satisfies the predicate.
Nat.find_min'- The witness `Nat.find H` is less than or equal to any natural number that satisfies the predicate.
- Classical logic (`classical`) is invoked to treat the existential predicate `P` as decidable, which Mathlib's `Nat.find` requires to construct the minimal natural number.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A feasible instance has a feasible schedule of minimum fetch cost over its horizon; turns the offline optimum into a concrete schedule. -/theorem deadline_paging_min_cost_schedule_exists {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (reqs : List (DeadlineRequest α)) (h : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ ∀ sched' : ℕ → Finset α, IsFeasibleSchedule k C₀ sched' reqs → scheduleCost sched (instanceHorizon reqs) ≤ scheduleCost sched' (instanceHorizon reqs) := by classical obtain ⟨s₀, hs₀⟩ := h let P : ℕ → Prop := fun n => ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = n have h_ex : ∃ n, P n := ⟨scheduleCost s₀ (instanceHorizon reqs), s₀, hs₀, rfl⟩ obtain ⟨sched, hsched_feas, hsched_cost⟩ := Nat.find_spec h_ex refine ⟨sched, hsched_feas, fun sched' hsched' => ?_⟩ rw [hsched_cost] exact Nat.find_min' h_ex ⟨sched', hsched', rfl⟩