A cover at the powers-of-two budget forces a satisfying literal choice
ProvedStableMSR.Recovery.Supplement.SATMetric.cover_iff_assignmentalgorithmsclusteringcomputational-complexity
The literal and private-point gadget has a cover by k balls with total radii at most the sum of the k powers of two exactly when one literal per variable covers every clause. Centers may be arbitrary vertices, with repetitions and arbitrary nonnegative real radii.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_SATMetric set_option autoImplicit false open StableMSR.Recovery StableMSR.Recovery.Supplement
Formal statement
namespace StableMSR.Recovery.Supplement.SATMetric
theorem cover_iff_assignment (k m : ℕ) (H : ℕ → Bool → ℕ → Bool) :
BallCover k m H ↔ ∃ s : Fin k → Bool, ∀ c : Fin m, ∃ i : Fin k, H i.val (s i) c.val = true := by sorry
end StableMSR.Recovery.Supplement.SATMetric
Source
Gibson, Kanade, Krohn, Pirwani, and Varadarajan, On Metric Clustering to Minimize the Sum of Radii, Algorithmica 57 (2010), Section 3, Theorem 2. https://www.cs.utsa.edu/~gibson/MetricKClustering.pdf . Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix C, https://arxiv.org/abs/2611.03547 . The explicit table used here adapts the literal and private-point construction to unrestricted finite metrics.