Lemma 26, p. 23 (Goel–Hann-Caruthers) — moving a point along its ray from the optimum keeps the optimum
ProvedLearnAugFL.CMP.lemma_26facility-locationgeometric-medianoptimalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Throughout, carries the Euclidean distance .
Let be a profile and an optimal location for the utilitarian cost . If and lies on the closed ray from through , i.e. for some , then is still an optimal location for the profile obtained by replacing with :
The lemma is the tool that lets the reduction move points towards (or away from) the optimum while keeping track of it.
Formalization Note The paper writes . Since optimal locations need not be unique (collinear profiles), this is read as " remains an optimal location".
Preamble
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
Formal statement
namespace LearnAugFL.CMP
theorem lemma_26 {n : ℕ} (P : Fin n → Pt) (o : Pt) (hP : IsOpt P o) (i : Fin n)
(hi : P i ≠ o) (t : ℝ) (ht : 0 ≤ t) :
IsOpt (Function.update P i (o + t • (P i - o))) o := by sorry
end LearnAugFL.CMP
Source
Agrawal, Balkanski, Gkatzelis, Ou & Tan, Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location, arXiv:2204.01120v1, Lemma 26 (citing Goel and Hann-Caruthers 2021), p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.