Weighted-input strong coresets for exact-k and at-most-k queries
DefinitionTightCoreset2027_Euclidean_Supplement_weightedCoresetsLet X be a finite subset of a metric space E, let u be its input weights, and let S⊆X have output weights w. For a nonempty finite ambient query C, reuse the published nearest-center distance and weighted clustering cost
An exact-k weighted-input strong ε-coreset satisfies
The separate at-most-k predicate imposes the same inequality for every finite ambient query with 1≤|C|≤k. Both predicates require S⊆X. Centers may lie anywhere in E. Input positivity and the valid parameter ranges are imposed by the using theorems; output weights are arbitrary nonnegative real numbers, represented by NNReal. Weights are functions on E whose values outside the respective finite set are ignored. Empty inputs and candidates are permitted. A zero true cost requires exact preservation. These predicates add no mass constraint or sampling law.
This extends the published unweighted-input model without changing its costs or its exact-k convention, and keeps the stronger query class of Lemma 4.1 separate.
import Definitions.Def_TightCoreset2027_Euclidean_coresetModel
set_option autoImplicit false
namespace TightCoreset2027.Euclidean.Supplement
/-- Definition 1.1 with positive input weights supplied by theorems: exact-k ambient queries. -/
def IsWeightedStrongCoreset {E : Type*} [MetricSpace E]
(z ε : ℝ) (k : ℕ) (X : Finset E) (u : E → NNReal)
(S : Finset E) (w : E → NNReal) : Prop :=
S ⊆ X ∧ ∀ C : Finset E, C.card = k →
|weightedCost z S w C - weightedCost z X u C| ≤ ε * weightedCost z X u C
/-- Lemma 4.1 preserves every nonempty ambient query with at most k distinct centers. -/
def IsWeightedAtMostCoreset {E : Type*} [MetricSpace E]
(z ε : ℝ) (k : ℕ) (X : Finset E) (u : E → NNReal)
(S : Finset E) (w : E → NNReal) : Prop :=
S ⊆ X ∧ ∀ C : Finset E, 1 ≤ C.card → C.card ≤ k →
|weightedCost z S w C - weightedCost z X u C| ≤ ε * weightedCost z X u C
end TightCoreset2027.Euclidean.Supplement