§7.1.2, (7.6)–(7.8) — complete threshold-cost chain
ProvedCompetitiveOnlinePD.WeightedCaching.threshold_cost_chainlinear-optimizationonline-algorithmsweighted-caching
Let 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 .
At the endpoint of every finite prefix , the entire chain holds for one common final interval vector:
Every interval sum ranges over . Both inequalities, the sum-exchange equality and the upper-bound penalty are included. This bounds the activation contribution using the actual arrays, without assuming a final row-tightness or cost inequality.
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
Preamble
import Definitions.Def_CompetitiveOnlinePD_WeightedCaching_Observables
Formal statement
namespace CompetitiveOnlinePD.WeightedCaching
open scoped BigOperators
theorem threshold_cost_chain
{P : Type} [Fintype P] [DecidableEq P]
(k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
(H : List P) :
let s := run k c H
thresholdCost k c H s ≤ slackWeighted k H s ∧
slackWeighted k H s = reordered k H s ∧
reordered k H s ≤ dualValue k H s := by sorry
end CompetitiveOnlinePD.WeightedCaching
Source
Buchbinder & Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach, copyright 2009, DOI:10.1561/0400000024, https://doi.org/10.1561/0400000024, (7.6)–(7.8), printed p.156 (PDF p.67); discussion printed p.157 (PDF p.68)