The Complexity of k-Means Clustering when Little is Known
Authors: Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Here, we study the complexity of k-means clustering in settings where most of the data is not known or simply irrelevant. To obtain a more fine-grained understanding of the tractability of this clustering problem, we apply the parameterized complexity paradigm and obtain three new algorithms for k-means clustering of incomplete data... |
| Researcher Affiliation | Academia | 1Algorithms and Complexity Group, TU Wien, Austria 2Institute of Informatics, University of Warsaw, Poland. |
| Pseudocode | No | The paper describes algorithmic procedures in prose and through mathematical notation within proofs, but it does not contain structured pseudocode or algorithm blocks (e.g., a clearly labeled Algorithm 1). |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with a dataset. While it mentions the Netflix Prize dataset as a motivating example ('The dataset is available at https://www.kaggle.com/netflix-inc/netflix-prize-data.'), it is not 'used in the experiments' as no experiments are reported. |
| Dataset Splits | No | The paper focuses on theoretical complexity and algorithm design, and thus does not describe experimental validation or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental procedures, therefore no specific hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity, and thus does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical aspects of k-means clustering and does not describe any specific experimental setup details or hyperparameters. |