§4.1 — the greedy eight-slot map ν, minimum-cost injections mc(T, O), and dist(s, X)
DefinitionFacilityIncompatibilities_UniformMatroid_Supplement_Congestionapproximation-algorithmsfacility-locationlocal-searchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be finite facility sets and . Write for the facility–facility distance.
- For a facility and a finite set , , with .
- For , with the family of injections ,
- The greedy map : fix for ; the elements of are targets, each with eight slots. Repeatedly select a globally shortest pair among unassigned and targets with an available slot, set and consume one slot; ties may be broken arbitrarily.
The predicate " is a greedy map" says that fixes and that there is an order of the elements of (the order of assignment) such that at every step : ; fewer than eight of are mapped to ; and for every and every target to which fewer than eight of 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 and take values in (ℝ≥0∞): the empty minimum is and exactly when no injection exists. is a function on all facilities; only its values on 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)