  Constructing small-sized coresets for various clustering problems in
different metric spaces has attracted significant attention for the past
decade. A central problem in the coreset literature is to understand what is
the best possible coreset size for $(k,z)$-clustering in Euclidean space. While
there has been significant progress in the problem, there is still a gap
between the state-of-the-art upper and lower bounds. For instance, the best
known upper bound for $k$-means ($z=2$) is $\min \{O(k^{3/2}
\varepsilon^{-2}),O(k \varepsilon^{-4})\}$ [1,2], while the best known lower
bound is $\Omega(k\varepsilon^{-2})$ [1].
  In this paper, we make significant progress on both upper and lower bounds.
For a large range of parameters (i.e., $\varepsilon, k$), we have a complete
understanding of the optimal coreset size. In particular, we obtain the
following results:
  (1) We present a new coreset lower bound $\Omega(k \varepsilon^{-z-2})$ for
Euclidean $(k,z)$-clustering when $\varepsilon \geq \Omega(k^{-1/(z+2)})$. In
view of the prior upper bound $\tilde{O}_z(k \varepsilon^{-z-2})$ [1], the
bound is optimal. The new lower bound also implies improved lower bounds for
$(k,z)$-clustering in doubling metrics.
  (2) For the upper bound, we provide efficient coreset construction algorithms
for $(k,z)$-clustering with improved or optimal coreset sizes in several metric
spaces. In particular, we provide an $\tilde{O}_z(k^{\frac{2z+2}{z+2}}
\varepsilon^{-2})$-sized coreset, with a unfied analysis, for
$(k,z)$-clustering for all $z\geq 1$ in Euclidean space.
  [1] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC'22.
  [2] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS'22.
