(22)–(24) — the modified objective satisfies
ProvedOnlineGND.eq_22_24competitive-analysisonline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1primal-dual
Consider GND with weighted power costs (, ), weights , , , and a -approximate min-cost oracle (). Run the online algorithm (20) with a parameter , and let be its final loads, , , and the dual solution of p.13:
Then the modified objective satisfies
This is the per-request accounting of the proof of Theorem 6, summed over all requests.
Differences from the source:
- generalization: the proof's parameter (with the condition it ensures for (17)) → any ; reason: (22)–(24) use only this condition, and satisfies it
- encoding: → ; reason: equal for since
- encoding: a -approximation algorithm → and the oracle predicate on the instance's requests; reason: an approximation factor of a minimization problem is at least
Preamble
import Definitions.Def_OnlineGND_DualFitting
Formal statement
namespace OnlineGND
/-- **(22)–(24)** (Nagarajan & Wang, arXiv:2007.07721v1, §4.1, proof of Theorem 6, p.13):
"So we obtain `Ā ≤ eτρ Σ_{i=1}^N yᵢ`." For the online algorithm (20) with parameter
`ρ ≥ (eα)^{α−1}` and a `τ`-approximate oracle, with final loads `A`, `L = Σ_{e∈E₁} cₑAₑ`,
`H = Σ_{e∈E∖E₁} cₑAₑ^{αₑ}` and the dual `yᵢ` of p.13,
`e ρ L + H ≤ e τ ρ Σᵢ yᵢ`.
**Formalization Note.** `α = alphaMax α`. The condition `ρ ≥ (eα)^{α−1}` is the one (17) uses (p.11);
it implies the paper's standing `ρ ≥ 1`. -/
theorem eq_22_24 {E : Type*} [Fintype E] [DecidableEq E] {N : ℕ} (c α : E → ℝ)
(hc : ∀ e, 0 ≤ c e) (hα : ∀ e, 1 ≤ α e) (reqs : Fin N → Request E)
(hw : ∀ i e, 1 ≤ (reqs i).w e) (τ : ℝ) (hτ : 1 ≤ τ) (O : Request E → (E → ℝ) → Finset E)
(hO : IsApproxOracle τ reqs O) (ρ : ℝ)
(hρ : (Real.exp 1 * alphaMax α) ^ (alphaMax α - 1) ≤ ρ) :
Real.exp 1 * ρ * costL c α (load reqs (powerAlg c α ρ O reqs))
+ costH c α (load reqs (powerAlg c α ρ O reqs)) ≤
Real.exp 1 * τ * ρ * ∑ i, dualY c α ρ (load reqs (powerAlg c α ρ O reqs)) (reqs i) := by sorry
end OnlineGND
Source
Nagarajan & Wang, Online Generalized Network Design Under (Dis)Economies of Scale, arXiv:2007.07721v1, §4.1, proof of Theorem 6, (22)–(24), p.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.