Theorem 3.2 (packing half, with the oracle) — the fractional routing scheme is feasible and 2 ln(P(max)+2)-competitive
ProvedBNCovPack.Routing.theorem_3_2Let be a finite set of edges with capacities , and let be a sequence of requests, each given by a finite list of paths (sets of edges) with at most edges each. Run the online fractional packing scheme with the oracle, with and , and let be the flows it produces. Then
- is a feasible fractional routing of (non-negative, at most per request, at most through each edge);
- for every feasible fractional routing of ,
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 and states Theorem 3.2 for general packing; its proof "follows along the same lines as the proof of Theorem 3.1" with replaced by , which with yields feasibility (claim (iii)) and the factor (claim (i) and weak duality). Only the packing half, on the routing instance, is stated; the covering half is not used by the mission.
import Mathlib import Definitions.Def_BNCovPack_Routing_Routing import Definitions.Def_BNCovPack_Routing_FracScheme
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.