WorksComputer Science
versus Clustering: When Does the Choice of Norm Matter?
Abstract
We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare -clustering in under the and objectives, defined as the sums of Manhattan and Euclidean distances, respectively. In the worst case, the elementary relationship between these norms yields a approximation bound, which is already tight for . We therefore investigate whether stronger guarantees are possible in a natural average-case model, where the dataset is arbitrary but the coordinate system is chosen uniformly at random among all orthonormal bases. Our main result shows that, when , with high probability over the random rotation, any -approximate clustering, with optimally chosen centers for its clusters, is also an -approximation under the objective. We also establish an expected approximation ratio of , yielding a dimension-independent bound of . We obtain analogous guarantees in the reverse direction, from to . We complement these results with lower bounds of in both directions, showing that our dimension-independent guarantees have asymptotically optimal dependence on for constant . Our proofs overcome the dependence of the algorithm's output on the random rotation using geometric projection arguments and small Euclidean coresets. In particular, our results provide guarantees for existing clustering algorithms without requiring their redesign.