Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4.1 — the greedy eight-slot map ν, minimum-cost injections mc(T, O), and dist(s, X)

Definition
FacilityIncompatibilities_UniformMatroid_Supplement_Congestion

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsfacility-locationlocal-searchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let P,O⊆VFP,O\subseteq V_FP,O⊆VF​ be finite facility sets and Q:=P∩OQ:=P\cap OQ:=P∩O. Write ddd for the facility–facility distance.

  1. For a facility sss and a finite set XXX, dist(s,X)=min⁡x∈Xd(s,x)\mathrm{dist}(s,X)=\min_{x\in X}d(s,x)dist(s,X)=minx∈X​d(s,x), with dist(s,∅):=+∞\mathrm{dist}(s,\emptyset):=+\inftydist(s,∅):=+∞.
  2. For T⊆PT\subseteq PT⊆P, with E(T,O)\mathcal E(T,O)E(T,O) the family of injections T→OT\to OT→O,
mc(T,O)=min⁡η∈E(T,O)∑s∈Td(s,η(s)).\mathrm{mc}(T,O)=\min_{\eta\in\mathcal E(T,O)}\sum_{s\in T}d(s,\eta(s)).mc(T,O)=η∈E(T,O)min​s∈T∑​d(s,η(s)).
  1. The greedy map ν:P→O\nu:P\to Oν:P→O: fix ν(q)=q\nu(q)=qν(q)=q for q∈Qq\in Qq∈Q; the elements of O∖QO\setminus QO∖Q are targets, each with eight slots. Repeatedly select a globally shortest pair (s,o)(s,o)(s,o) among unassigned s∈P∖Qs\in P\setminus Qs∈P∖Q and targets ooo with an available slot, set ν(s)=o\nu(s)=oν(s)=o and consume one slot; ties may be broken arbitrarily.

The predicate "ν\nuν is a greedy map" says that ν\nuν fixes QQQ and that there is an order s0,…,sk−1s_0,\dots,s_{k-1}s0​,…,sk−1​ of the elements of P∖QP\setminus QP∖Q (the order of assignment) such that at every step ttt: ν(st)∈O∖Q\nu(s_t)\in O\setminus Qν(st​)∈O∖Q; fewer than eight of s0,…,st−1s_0,\dots,s_{t-1}s0​,…,st−1​ are mapped to ν(st)\nu(s_t)ν(st​); and d(st,ν(st))≤d(su,o)d(s_t,\nu(s_t))\le d(s_u,o)d(st​,ν(st​))≤d(su​,o) for every u≥tu\ge tu≥t and every target ooo to which fewer than eight of s0,…,st−1s_0,\dots,s_{t-1}s0​,…,st−1​ are mapped. These are exactly the outputs of the procedure under all tie-breaking rules.

These objects enter Lemma 16, the simultaneous subset bound behind Theorem 4.

Formalization Note dist\mathrm{dist}dist and mc\mathrm{mc}mc take values in R≥0∪{∞}\mathbb R_{\ge0}\cup\{\infty\}R≥0​∪{∞} (ℝ≥0∞): the empty minimum is +∞+\infty+∞ and mc(T,O)=∞\mathrm{mc}(T,O)=\inftymc(T,O)=∞ exactly when no injection exists. ν\nuν is a function on all facilities; only its values on PPP matter.

Definition code
import Mathlib
import Definitions.Def_FacilityIncompatibilities_UniformMatroid_Model

open scoped ENNReal

namespace FacilityIncompatibilities.UniformMatroid.Supplement

variable {C F : Type*}

/-- `dist(s, X) = min_{x ∈ X} d(s, x)` for a facility `s` and a finite facility set `X`
(§4.1, printed p.15 / PDF p.16), with `dist(s, ∅) := +∞`.

**Formalization Note** Valued in `ℝ≥0∞`: the infimum over the empty set is `⊤ = +∞`, the
paper's convention, never a junk `0`. -/
noncomputable def setDist (I : Instance C F) (s : F) (X : Finset F) : ℝ≥0∞ :=
  ⨅ x ∈ X, ENNReal.ofReal (I.fdist s x)

/-- `mc(T, O) = min_{η ∈ E(T, O)} ∑_{s ∈ T} d(s, η(s))` (§4.1, printed p.15 / PDF p.16): the
minimum total facility–facility distance of an injection `η : T → O`.

**Formalization Note** Valued in `ℝ≥0∞`; it is `⊤` exactly when there is no injection
(`|T| > |O|`), otherwise the infimum is over a finite nonempty set and is attained. -/
noncomputable def mc (I : Instance C F) (T O : Finset F) : ℝ≥0∞ :=
  ⨅ (η : T → O) (_ : Function.Injective η), ENNReal.ofReal (∑ s : T, I.fdist s (η s))

/-- **The greedy bounded-congestion map** `ν : P → O` of §4.1 (printed pp.14–15 / PDF pp.15–16),
with `Q = P ∩ O`: `ν(q) = q` for `q ∈ Q`; the targets are `O \ Q`, each with eight slots;
repeatedly a globally shortest pair `(s, o)` is selected among unassigned `s ∈ P \ Q` and
targets `o ∈ O \ Q` with an available slot, `ν(s) := o`, and one slot is consumed (ties
arbitrary).

`IsGreedyMap I P O ν` says that `ν` is an output of this procedure for some tie-breaking: `ν`
fixes `Q`, and there is an enumeration `s_0, …, s_{k−1}` (a duplicate-free list) of `P \ Q`, the
order of assignment, such that for every step `t`:
* `ν(s_t)` is a target in `O \ Q`;
* fewer than eight of `s_0, …, s_{t−1}` were assigned to `ν(s_t)` (a slot was available);
* `d(s_t, ν(s_t)) ≤ d(s_u, o)` for every still unassigned `s_u` (`u ≥ t`) and every target `o`
  with fewer than eight of `s_0, …, s_{t−1}` assigned to it (the pair is globally shortest). -/
def IsGreedyMap [DecidableEq F] (I : Instance C F) (P O : Finset F) (ν : F → F) : Prop :=
  (∀ q ∈ P ∩ O, ν q = q) ∧
  ∃ l : List F, l.Nodup ∧ l.toFinset = P \ (P ∩ O) ∧
    ∀ (t : ℕ) (ht : t < l.length),
      ν l[t] ∈ O \ (P ∩ O) ∧
      (l.take t).countP (fun u => decide (ν u = ν l[t])) < 8 ∧
      ∀ (u : ℕ) (hu : u < l.length), t ≤ u → ∀ o ∈ O \ (P ∩ O),
        (l.take t).countP (fun u' => decide (ν u' = o)) < 8 →
        I.fdist l[t] (ν l[t]) ≤ I.fdist l[u] o

end FacilityIncompatibilities.UniformMatroid.Supplement
Source
Pengfei Wu, Zachary Friggstad, Facility Location with Customer Incompatibilities, STOC 2027 submission #664 (October 2026), SHA-256 e95d28b65476bd15332cddbb49bb8bfb3c370bb260b03d92b35425595cdb7ab3, §4.1, printed pp.14–15 / PDF pp.15–16 (construction of ν, definition of mc(T, O), dist(s, ∅) := +∞ in Lemma 16)

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