Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 (packing half, with the oracle) — the fractional routing scheme is feasible and 2 ln(P(max)+2)-competitive

Proved
BNCovPack.Routing.theorem_3_2

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualrouting

Let EEE be a finite set of edges with capacities u(e)>0u(e) > 0u(e)>0, and let σ\sigmaσ be a sequence of requests, each given by a finite list of paths (sets of edges) with at most P(max⁡)P(\max)P(max) edges each. Run the {0,1}\{0,1\}{0,1} online fractional packing scheme with the oracle, with ℓ=P(max⁡)+1\ell = P(\max)+1ℓ=P(max)+1 and B′=2ln⁡(1+ℓ)=2ln⁡(P(max⁡)+2)B' = 2\ln(1+\ell) = 2\ln(P(\max)+2)B′=2ln(1+ℓ)=2ln(P(max)+2), and let falgf^{\mathrm{alg}}falg be the flows it produces. Then

  1. falgf^{\mathrm{alg}}falg is a feasible fractional routing of σ\sigmaσ (non-negative, at most 111 per request, at most u(e)u(e)u(e) through each edge);
  2. for every feasible fractional routing fff of σ\sigmaσ,
val(f)≤2ln⁡(P(max⁡)+2)⋅val(falg).\mathrm{val}(f) \le 2\ln\big(P(\max)+2\big) \cdot \mathrm{val}(f^{\mathrm{alg}}).val(f)≤2ln(P(max)+2)⋅val(falg).

This is the first phase of the two-phase approach of Section 5.2: a feasible fractional routing within a logarithmic factor of the fractional optimum, produced online.

Formalization Note The paper writes O(log⁡ℓ)O(\log \ell)O(logℓ) and states Theorem 3.2 for general {0,1}\{0,1\}{0,1} packing; its proof "follows along the same lines as the proof of Theorem 3.1" with nnn replaced by ℓ\ellℓ, which with B′=2ln⁡(1+ℓ)B' = 2\ln(1+\ell)B′=2ln(1+ℓ) yields feasibility (claim (iii)) and the factor B′=2ln⁡(1+ℓ)B' = 2\ln(1+\ell)B′=2ln(1+ℓ) (claim (i) and weak duality). Only the packing half, on the routing instance, is stated; the covering half is not used by the mission.

Preamble
import Mathlib
import Definitions.Def_BNCovPack_Routing_Routing
import Definitions.Def_BNCovPack_Routing_FracScheme
Formal statement
namespace BNCovPack.Routing

/-- Theorem 3.2 (packing half, with the oracle remark), Buchbinder–Naor 2009, p. 5, on the
routing problem of §5.2 (Fig. 3, p. 14). Let `E` be a finite set of edges with capacities
`u e > 0`, let every path of every request have at most `Pmax` edges, and run the `{0,1}`
fractional scheme with `ℓ = Pmax + 1` and `B' = 2 ln(1 + ℓ) = 2 ln(Pmax + 2)` on the request
sequence `σ`. Then the flows it produces form a feasible fractional routing of `σ`, and every
feasible fractional routing `f` of `σ` has value at most `2 ln(Pmax + 2)` times the scheme's. -/
theorem theorem_3_2 {E : Type*} [Fintype E] [DecidableEq E] (u : E → ℝ) (hu : ∀ e, 0 < u e)
    (Pmax : ℕ) (σ : List (List (Finset E))) (hP : ∀ ps ∈ σ, ∀ P ∈ ps, P.card ≤ Pmax) :
    IsFeasibleRouting u σ (fracRun u (Pmax + 1) (2 * Real.log ((Pmax : ℝ) + 2)) σ).flows ∧
    ∀ f : List (List ℝ), IsFeasibleRouting u σ f →
      routingValue f ≤ 2 * Real.log ((Pmax : ℝ) + 2) *
        routingValue (fracRun u (Pmax + 1) (2 * Real.log ((Pmax : ℝ) + 2)) σ).flows := by sorry

end BNCovPack.Routing
Source
Buchbinder, Naor, Online Primal-Dual Algorithms for Covering and Packing, Math. Oper. Res. (2009), DOI 10.1287/moor.1080.0363, p. 5, Theorem 3.2 and the oracle remark; applied as in Section 5.2, p. 15
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me