For many problems, the running time of \(\mathcal {O}^*(2^n)\)  is often achievable by a brute-force enumeration of all the solutions. However, for many \(\operatorname{{\sf NP}}\) -hard problems, it is often possible to obtain improved running times. The field of exact algorithms for \(\operatorname{{\sf NP}}\) -hard problems is several decades old. In 2003, Woeginger wrote a survey [1]} on this topic, which revived the field. This eventually led to a plethora of new results and techniques, such as subset convolution [2]}, measure and conquer [3]}, and monotone local search [4]}. A detailed survey on this topic can be found in a textbook by Kratsch and Fomin [5]}. We study the aforementioned classical clustering problems from this perspective. In other words, we ask whether the classical clustering problems such as \(k\) -median and \(k\) -means admit moderately exponential-time algorithms, i.e., algorithms with running time \(c^n \cdot n^{\mathcal {O}(1)}\)  for a constant \(c < 2\)  that is as small as possible. We indeed answer this question in the affirmative, leading to the following theorem.
