Abstract: We consider the well-studied algorithmic regime of designing a

(1+ϵ)-approximation algorithm for a k-clustering problem that runs in time f(k, ϵ)poly(n). Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, ℓ-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics). Key to our approach is a new concept that we call bounded ϵ-scatter dimension – an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.