Submodular Clustering beyond $1-1/e$

Submodular clustering provides a flexible framework for modeling coverage and representation quality in metric spaces, capturing a broad range of objectives arising in machine learning, including influence maximization, data summarization, and representation learning. Given a set of points $P$ in a metric space and a decreasing service function $\phi$, the goal is to select $k$ centers $U$ to maximize total service $\sum_{p \in P} \phi(d(U, p))$, where $d(U, p)$ is the distance from $p$ to its nearest center. While this objective is submodular and admits a standard $1 - 1/e$ approximation via greedy algorithms, it has remained unclear whether and when this barrier can be surpassed. We resolve this question by characterizing exactly which functions $\phi$ permit approximation guarantees beyond $1-1/e$. We identify a natural parameter $\gamma_\phi$ capturing how rapidly $\phi$ decreases, and show that, assuming $\mathrm{P} \ne \mathrm{NP}$, a better-than $1-1/e$ approximation ratio is achievable in polynomial time if and only if $\gamma_\phi > 0$.