Lemma 8.8: the -center value is at most iff the set covering problem with radius needs at most facilities
ProvedSupplyChainTheory.pcenter_set_coverLemma 8.8. Let and . The optimal objective value of the (vertex) -center problem is at most if and only if the optimal objective value of the set covering location problem with coverage radius is at most , i.e., some set of at most sites has every customer within distance of one of its members.
The book omits the proof (Problem 8.47). A -set with maximum assigned distance at most covers within ; a cover with fewer than sites can be padded to exactly without increasing any assigned distance. This is the basis of the bisection algorithm for the -center problem, which solves a set covering problem at each radius.
Formalization Note The set covering value is stated through its feasible solutions rather than as a natural-number infimum, whose value on an infeasible instance would be .
import Definitions.Def_SupplyChainTheory_location
namespace SupplyChainTheory
theorem pcenter_set_cover {n m : ℕ} (c : Fin n → Fin m → ℝ) (p : ℕ) (hp : 1 ≤ p) (hpm : p ≤ m)
(r : ℝ) (hr : 0 ≤ r) :
pCenterValue c p ≤ r ↔ ∃ S : Finset (Fin m), S.card ≤ p ∧ ∀ i, ∃ j ∈ S, c i j ≤ r := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.