Improved Coresets for Euclidean $k$-Means
Authors: Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we improve these bounds to O(min(k3/2 ε 2, k ε 4)) for Euclidean k-means and O(min(k4/3 ε 2, k ε 4)) for Euclidean k-median. In particular, ours is the first provable bound that breaks through the k2 barrier while retaining an optimal dependency on ε. |
| Researcher Affiliation | Collaboration | Vincent Cohen-Addad Google Research Kasper Green Larsen Aarhus University David Saulpic University of Vienna Chris Schwiegelshohn Aarhus University Omar Ali Sheikh-Omar Aarhus University |
| Pseudocode | No | The paper describes algorithmic concepts and procedures but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and focuses on proving bounds; it does not mention releasing source code for the described methodology or provide any links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not report on experiments using specific datasets, thus no information on publicly available training datasets or their access is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments, so no training, validation, or test dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation details or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or provide details such as hyperparameters. |