Average Sensitivity of Euclidean k-Clustering
Authors: Yuichi Yoshida, Shinji Ito
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Given a set of n points in Rd, the goal of Euclidean (k, ℓ)-clustering is to find k centers that minimize the sum of the ℓ-th powers of the Euclidean distance of each point to the closest center. ... We first show that a popular algorithm k-MEANS++ and its variant called Dℓ-SAMPLING have low average sensitivity. Next, we show that any approximation algorithm for Euclidean (k, ℓ)-clustering can be transformed to an algorithm with low average sensitivity while almost preserving the approximation guarantee. As byproducts of our results, we provide several algorithms for consistent (k, ℓ)-clustering and dynamic (k, ℓ)-clustering in the random-order model... |
| Researcher Affiliation | Collaboration | Yuichi Yoshida National Institute of Informatics JST, PRESTO yyoshida@nii.ac.jp Shinji Ito NEC i-shinji@nec.com |
| Pseudocode | Yes | Algorithm 1: Dℓ-sampling for Euclidean (k, ℓ)-clustering |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a repository. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental data splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |