Theorem 6 — with a τ-approximate oracle, and
ProvedOnlineGND.theorem_6competitive-analysisnetwork-designonline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Consider GND with weighted power costs (, ), weights , , , and a -approximate min-cost oracle (). Run the online algorithm (20) with , and let be its final loads, and . Then:
- the algorithm chooses a reply in for every request ;
- it is -competitive: ;
- ;
- ;
- .
Each bound holds with replaced by the cost of any solution .
The separate bound on the linear part , with factor instead of , is what §5 needs to obtain the additive form in Theorem 1.
Differences from the source:
- generalization: the three printed bounds → the same bounds plus clause 5, the combined bound proved on p.14, and clause 1; reason: extra conclusions; dropping them gives the printed theorem
- encoding: "there is a polynomial time online algorithm" and OPT → the algorithm (20) with , a deterministic online recursion making one oracle call per request, compared against every solution; reason: the paper's own algorithm; the running time is carried by the shape of the definition, and OPT is the minimum over solutions
- 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_Doubled
Formal statement
namespace OnlineGND
/-- **Theorem 6** (Nagarajan & Wang, arXiv:2007.07721v1, §4.1, p.12; proof pp.12–14). For GND with
weighted power costs `cₑ x^{αₑ}` and a `τ`-approximate min-cost oracle, the online algorithm (20)
with `ρ = (eτα)^{α−1}` chooses a reply in each `𝒫ᵢ`, is `2(eατ)^α`-competitive, and with
`L = Σ_{e∈E₁} cₑAₑ`, `H = Σ_{e∈E∖E₁} cₑAₑ^{αₑ}`:
`L ≤ 2τ · OPT`, `H ≤ 2(eατ)^α · OPT`, and (p.14) `L/τ + H/(eτα)^α ≤ 2 · OPT`.
Each bound is against the cost of every reply profile.
**Formalization Note.** `α = alphaMax α`, `E₁ = {e : αₑ = 1}`. The algorithm's cost is `L + H`. -/
theorem theorem_6 {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) (sol : Fin N → Finset E) (hsol : IsReplyProfile reqs sol) :
IsReplyProfile reqs (powerAlg c α (rhoStar τ α) O reqs) ∧
costL c α (load reqs (powerAlg c α (rhoStar τ α) O reqs))
+ costH c α (load reqs (powerAlg c α (rhoStar τ α) O reqs)) ≤
2 * (Real.exp 1 * alphaMax α * τ) ^ alphaMax α * powerCost c α (load reqs sol) ∧
costL c α (load reqs (powerAlg c α (rhoStar τ α) O reqs)) ≤
2 * τ * powerCost c α (load reqs sol) ∧
costH c α (load reqs (powerAlg c α (rhoStar τ α) O reqs)) ≤
2 * (Real.exp 1 * alphaMax α * τ) ^ alphaMax α * powerCost c α (load reqs sol) ∧
costL c α (load reqs (powerAlg c α (rhoStar τ α) O reqs)) / τ
+ costH c α (load reqs (powerAlg c α (rhoStar τ α) O reqs))
/ (Real.exp 1 * τ * alphaMax α) ^ alphaMax α ≤
2 * powerCost c α (load reqs sol) := by sorry
end OnlineGND
Source
Nagarajan & Wang, Online Generalized Network Design Under (Dis)Economies of Scale, arXiv:2007.07721v1, Theorem 6, p.12; proof pp.12–14 (ρ and the combined bound p.14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.