§7.1.2, (7.3) — positive-coordinate complementary slackness
ProvedCompetitiveOnlinePD.WeightedCaching.positive_slacklinear-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 every reached state and every valid interval,
This gives the threshold-cost complementary-slackness condition without imposing it on the state or asserting positivity of an untouched coordinate.
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
- 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 positive_slack
{P : Type} [Fintype P] [DecidableEq P]
(k : ℕ) (hk : 1 ≤ k) (c : P → ℝ) (hc : ∀ p, 1 ≤ c p)
(H : List P) (s : State P) (hs : reached k c H s) :
∀ v ∈ intervals H,
(0 < s.x v.1 v.2 ↔ 0 < truncated k s.x v.1 v.2) ∧
(0 < s.x v.1 v.2 → c v.1 ≤ slack H s v.1 v.2) := 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.3), printed p.155 (PDF p.66)