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 $\varphi$, the goal is to select $k$ centers $U$ to maximize total service ${\sum }_{p\in P}\varphi (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 $\varphi$ permit approximation guarantees beyond $1-1/e$. We identify a natural parameter ${\gamma }_{\varphi }$ capturing how rapidly $\varphi$ 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 }_{\varphi }>0$.