Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation

Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn

In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key rol…