Theorem 7.1 — full fractional weighted caching guarantee
ProvedCompetitiveOnlinePD.WeightedCaching.fractional_caching_competitiveLet be a finite universe of unit-size pages, let be an integer, and let be arbitrary real costs. A finite request list has no prescribed horizon or restriction on repetitions or on relative to . All states below are computed by the shared prefix algorithm. Write for its interval slack, for its unscaled dual objective, and .
The prefix-defined fractional caching algorithm completes every request at its first capacity-satisfying finite real clock. An initially satisfied row causes no update. Each stopping set used is nonempty, bounded below and attains its infimum. At every prefix the interval assignment is LP-feasible, resident fractions lie in , the requested page is fully resident and total resident mass is at most . Existing coordinates increase monotonically, closed coordinates stay frozen, and future dual coordinates remain zero. States at a revealed prefix agree across all continuations.
For every finite prefix and every fractional assignment satisfying its capacity rows and ,
At every live state the algorithm also satisfies the full live (7.4):
with and evaluated at that same state, including a pre-stop event side when unsatisfied.
The primary inequality uses eviction charges. For the independently computed fetching ledger and terminal weighted resident mass , the goal also states
and
Here is the corresponding offline fetching cost. This supplies the sequence-independent additive term allowed by §2.3. The empty prefix, , repeated requests, unequal real costs and are all included. No stopping, feasibility, slackness or competitive guarantee is assumed.
Differences from the source:
- encoding: finite unit-page universes and arbitrary request prefixes → a finite page type, finite lists and one-based natural indices restricted to valid requests and occurrence intervals; reason: every finite prefix is included, also the empty list; no final horizon or future request is an input to a transition
- encoding: the next request time in the interval sums → the absent next occurrence is T+1 solely as a summation sentinel; reason: last intervals include all intervening requests through T; the sentinel is never a request
- reading: the boxed parenthetical r(p_t,t) < t′ < r(p_t,t)+1 → updates between occurrence request times t(p,j)+1 and t(p,j+1)-1; reason: the consecutive counters admit no integer update time; printed p.152 specifies the intended lifetime
- encoding: continuous updates until capacity is satisfied → an exact real scalar flow with simultaneous events, first-stop infimum and left/right activation states; reason: this gives the stated zero, jump, exponential and saturation rules without discretization; completion is a conclusion
- reading: no visible operator between the two printed dual-objective sums → the second sum is subtracted; reason: equation (7.8), the dual constraints and the dual-profit derivatives fix the minus sign
- encoding: inconsistent dummy page letters i,p and an overloaded time t → bound page variables and distinct horizon and row times; reason: the capacity rows and (7.6) bind the intended variables without changing any instance
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators
theorem fractional_caching_competitive
{P : Type} [Fintype P] [DecidableEq P]
(k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
(H : List P) :
(∀ (h : List P) (p : P), completes k c h p) ∧
(∀ h : List P, feasible k h (run k c h).x ∧
(∀ p, 0 ≤ resident h (run k c h).x p ∧ resident h (run k c h).x p ≤ 1) ∧
(∑ p, resident h (run k c h).x p) ≤ (k : ℝ)) ∧
(∀ (h : List P) (p : P), resident (h ++ [p]) (run k c (h ++ [p])).x p = 1) ∧
(∀ (h tail : List P) (v : P × ℕ), v ∈ intervals h →
(run k c h).x v.1 v.2 ≤ (run k c (h ++ tail)).x v.1 v.2) ∧
(∀ (h tail : List P) (p : P) (j : ℕ), 1 ≤ j → j < h.count p →
(run k c (h ++ tail)).x p j = (run k c h).x p j ∧
(run k c (h ++ tail)).z p j = (run k c h).z p j) ∧
(∀ (h : List P) (p : P) (a b : ℝ) (beforeA beforeB : Bool),
row (h ++ [p]) (h.length+1) (introduce h p (run k c h)).x <
required k (h ++ [p]) →
0 ≤ a → a < b → b ≤ duration k c h p (run k c h) →
∀ v ∈ intervals (h ++ [p]),
(clock beforeA k c h p (run k c h) a).x v.1 v.2 ≤
(clock beforeB k c h p (run k c h) b).x v.1 v.2) ∧
(∀ (h : List P) (s : State P), reached k c h s →
(∀ v ∈ intervals h, 0 ≤ s.x v.1 v.2 ∧ s.x v.1 v.2 ≤ 1) ∧
(∀ t, h.length < t → s.y t = 0)) ∧
(∀ (h tail : List P) (t : ℕ), t ≤ h.length →
run k c ((h ++ tail).take t) = run k c (h.take t)) ∧
(∀ (h : List P) (p : P) (τ : ℝ) (before : Bool), live before k c h p τ →
liveInequality k (h ++ [p]) (clock before k c h p (run k c h) τ)) ∧
(∀ u : IntervalArray P, feasible k H u →
cost c H (run k c H).x ≤ 2 * (1 + Real.log (k : ℝ)) * cost c H u) ∧
fetchingCost k c H - cost c H (run k c H).x =
residentValue c H (run k c H).x ∧
(0 ≤ residentValue c H (run k c H).x ∧
residentValue c H (run k c H).x ≤ ∑ p, c p) ∧
(∀ u : IntervalArray P, feasible k H u →
fetchingCost k c H ≤
2 * (1 + Real.log (k : ℝ)) * (cost c H u + residentValue c H u) + ∑ p, c p) := by sorry
end CompetitiveOnlinePD.WeightedCaching