deadline_paging_feasible_sublist
Feasibility of a schedule for a request list passes to any sublist of the requests.
Statement
theorem deadline_paging_feasible_sublist {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α) {reqs reqs' : List (DeadlineRequest α)} (hsub : reqs' ⊆ reqs) (h : IsFeasibleSchedule k C₀ sched reqs) : IsFeasibleSchedule k C₀ sched reqs'
- Source
- step towards deadline_paging_optimal_competitive_ratio_two_holes
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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
Feasibility of a schedule requires an initial cache condition, a capacity bound at each step, and timely satisfaction of every request in the list. The first two requirements are independent of the request sequence, while every request in a sublist is already present in the original list. The proof directly reuses the initial state and capacity bounds from the original feasibility hypothesis, and applies its request-satisfaction guarantee to each request in the sublist via the inclusion `reqs' ⊆ reqs`.
The schedule `sched` is feasible for the sublist `reqs'`.
A schedule is feasible for `reqs'` if: (1) its initial configuration is `C₀`, (2) the cache capacity `k` is respected at all times, and (3) every request in `reqs'` is served between its arrival and deadline. The first two conditions do not depend on the request list and hold directly from the feasibility of `sched` for `reqs` (`h.1` and `h.2.1`). For the third condition, given any request `r ∈ reqs'`, the assumption `hsub` implies `r ∈ reqs`, so the service guarantee from feasibility on `reqs` (`h.2.2`) applies directly. Combining these three facts establishes feasibility for `reqs'`.
IsFeasibleSchedule k C₀ sched reqs' := ⟨h.1, h.2.1, fun r hr => h.2.2 r (hsub hr)⟩
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Feasibility is inherited by sublists, hence in particular by arrival prefixes. -/theorem deadline_paging_feasible_sublist {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α) {reqs reqs' : List (DeadlineRequest α)} (hsub : reqs' ⊆ reqs) (h : IsFeasibleSchedule k C₀ sched reqs) : IsFeasibleSchedule k C₀ sched reqs' := ⟨h.1, h.2.1, fun r hr => h.2.2 r (hsub hr)⟩