Proof of Theorem 3, pp. 37–38 —
ProvedProductFraming.Nest.gamma_ge_six_div_pi_sqbound-revealing-programp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-framing
Fix . Every feasible solution of the bound-revealing program (5) has objective value at least :
Equivalently, the optimal value of (5) satisfies .
This is the bound-revealing core of the analysis: combined with Theorem 2, Proposition 1 and Lemma 2 it gives Theorem 3.
Formalization Note The statement avoids naming by quantifying over all feasible solutions; .
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Program
Formal statement
namespace ProductFraming.Nest
open Finset
/-- Proof of Theorem 3, conclusion (Gallego, Li, Truong, Wang 2020, A.2, pp. 37–38): `γ ≥ 6/π²`,
i.e. every feasible solution of (5) has objective value at least `6/π²`. -/
theorem gamma_ge_six_div_pi_sq (m : ℕ) (hm : 1 ≤ m) :
∀ U Λ : ℕ → ℝ, Feasible5 m U Λ → 6 / Real.pi ^ 2 ≤ J5 hm U Λ := by sorry
end ProductFraming.Nest
Source
Gallego, Li, Truong, Wang, Approximation Algorithms for Product Framing and Pricing, Operations Research (2020), DOI 10.1287/opre.2019.1875, authors' accepted manuscript, A.2, Proof of Theorem 3, pp. 37–38
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.