Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Proposition 3, p. 21 — ε-equitable district error bound with corrected η

Proved
CarlssonPartition.Approx.proposition_3

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

heavy-trafficp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1region-partitioningvehicle-routing

Consider a compact convex service region with normalized Lipschitz demand density, mmm identical vehicles, a depot, capacity qqq, speed vvv, mean service time sˉ\bar ssˉ, and geometric constant β\betaβ. Let R1,…,RmR_1,\ldots,R_mR1​,…,Rm​ partition the region and let their μ1\mu_1μ1​ and μ2\mu_2μ2​ shares differ from one mmmth of the corresponding whole-region shares by at most ε\varepsilonε. For λ>0\lambda>0λ>0 in the stable regime, ε≥0\varepsilon\ge0ε≥0, and corrected η<1\eta<1η<1, write LiL_iLi​ for the single-vehicle Theorem 3 leading term using district iii's own arrival rate and conditional density and L∗L^*L∗ for the full-region term. Then

∣Li−L∗∣≤4η(1−η)2L∗for every i.\lvert L_i-L^*\rvert\le \frac{4\eta}{(1-\eta)^2}L^*\qquad\text{for every }i.∣Li​−L∗∣≤(1−η)24η​L∗for every i.

The bound quantifies the loss in each district from approximate equitability.

Formalization Note The source prints η=ε/max⁡{μ1(R)/m,(vq/λ)(1−λμ2(R)/(mvq))}\eta=\varepsilon/\max\{\mu_1(R)/m,(vq/\lambda)(1-\lambda\mu_2(R)/(mvq))\}η=ε/max{μ1​(R)/m,(vq/λ)(1−λμ2​(R)/(mvq))}, which makes the proposition false; the formal statement uses min⁡\minmin as the proof requires. Its “for small ε\varepsilonε” is expressed as η<1\eta<1η<1. LiL_iLi​ and L∗L^*L∗ are Theorem 3 leading expressions at fixed λ\lambdaλ, rather than the underlying stochastic delivery-time functions.

Preamble
import Mathlib
import Definitions.Def_CarlssonPartition_Approx_Setting
Formal statement
namespace CarlssonPartition.Approx

theorem proposition_3 (I : Instance) (hI : I.Standing)
    (Rs : Fin I.m → Set CarlssonPartition.Equitable.Plane) (hP : I.IsPartition Rs)
    (lam ε : ℝ) (hlam : 0 < lam)
    (hstab : I.workload I.m lam I.R I.f < 1)
    (hε : 0 ≤ ε)
    (h1 : ∀ i, |I.mu1 (Rs i) - (1 / (I.m : ℝ)) * I.mu1 I.R| ≤ ε)
    (h2 : ∀ i, |I.mu2 (Rs i) - (1 / (I.m : ℝ)) * I.mu2 I.R| ≤ ε)
    (hη : I.eta lam ε < 1) :
    ∀ i, |I.bvrLeading 1 (I.lamSub lam (Rs i)) (Rs i) (I.fSub (Rs i)) -
      I.bvrLeading I.m lam I.R I.f| ≤
      4 * I.eta lam ε / (1 - I.eta lam ε) ^ 2 *
        I.bvrLeading I.m lam I.R I.f := by sorry
end CarlssonPartition.Approx
Source
Carlsson, Liu, Salari and Yu, Provably Good Region Partitioning for On-Time Last-Mile Delivery, accepted manuscript (SSRN 3915544; published in Operations Research 72(1):91–109, 2024, doi:10.1287/opre.2021.0588), p. 21, Proposition 3 (PDF 22); proof pp. ec12–ec13 (PDF 49–50)
Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 16, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me