§5, p.14 —
ProvedOnlineGND.opt_J_le_two_opt_Ieconomies-of-scalenetwork-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a GND instance with (D)oS costs (, , ) and weights , and let be the power-cost instance of §5, with copies of each resource, , , , . For every solution of with loads , the reply profile of that uses both copies of each resource of is a solution of , and its cost satisfies
Hence .
The bound transfers Theorem 6 on back to the original instance.
Differences from the source:
- encoding: → every solution of lifts to a solution of of at most twice its cost; reason: equivalent, since OPT is the minimum over finitely many solutions
- encoding: → ; reason: , used in , is undefined at
- encoding: resources → ; reason: a labelling of the copies
- encoding: in at , → the value (
Real.rpow); reason: Lean convention , the limit of as ; it changes no instance with or
Preamble
import Definitions.Def_OnlineGND_Doubled
Formal statement
namespace OnlineGND
/-- **`OPT_𝒥 ≤ 2 · OPT_𝓘`** (Nagarajan & Wang, arXiv:2007.07721v1, §5, p.14, from the first inequality
of Lemma 1): every reply profile `p*` of the (D)oS instance `𝓘` (weights `≥ 1`) lifts to a reply
profile of the power-cost instance 𝒥 whose cost `Σ_{r∈E′} c_r (ℓ_r)^{α_r} = Σₑ hₑ(ℓ*ₑ)` is at most
`2 Σₑ fₑ(ℓ*ₑ)`.
**Formalization Note.** `𝒥` has resources `E × Bool`, requests `liftReq (reqs i)`, scalars `cJ` and
exponents `alphaJ`. The minimum over profiles is stated profile by profile. -/
theorem opt_J_le_two_opt_I {E : Type*} [Fintype E] [DecidableEq E] {N : ℕ} (σ ξ α : E → ℝ)
(hσ : ∀ e, 0 ≤ σ e) (hξ : ∀ e, 0 < ξ e) (hα : ∀ e, 1 ≤ α e) (reqs : Fin N → Request E)
(hw : ∀ i e, 1 ≤ (reqs i).w e) (sol : Fin N → Finset E) (hsol : IsReplyProfile reqs sol) :
IsReplyProfile (fun i => liftReq (reqs i)) (fun i => liftSet (sol i)) ∧
powerCost (cJ σ ξ α) (alphaJ α)
(load (fun i => liftReq (reqs i)) (fun i => liftSet (sol i))) ≤
2 * ∑ e, dosCost σ ξ α e (load reqs sol e) := by sorry
end OnlineGND
Source
Nagarajan & Wang, Online Generalized Network Design Under (Dis)Economies of Scale, arXiv:2007.07721v1, §5, p.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.