Clustering What Matters: Optimal Approximation for Clustering with Outliers
Authors: Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) n O(1) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-MEDIAN and k-MEANS with outliers in general metrics. |
| Researcher Affiliation | Academia | 1 Indian Institute of Technology Madras, Chennai, India. 2 University of Bergen, Bergen, Norway 3 The Institute of Mathematical Sciences, HBNI, Chennai, India 4 New York University Shanghai, China |
| Pseudocode | No | The algorithm steps are described procedurally in paragraph form (e.g., 'We enumerate every subset T S of size at most m. For each T, we compute a β-approximation solution...'), but there is no formally structured pseudocode block, algorithm box, or figure labeled as such. |
| Open Source Code | No | A full version of the paper containing missing proofs and other details can be found is available on ar Xiv:2212.00696 (Agrawal et al. 2022). This refers to a paper version, not code. There is no explicit statement about releasing code or a link to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and approximation proofs, and as such, it does not use or refer to any specific dataset for training, validation, or testing. |
| Dataset Splits | No | This is a theoretical paper focused on algorithm design and approximation proofs, and as such, it does not specify any dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper focused on algorithm design and approximation proofs, and as such, it does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper focused on algorithm design and approximation proofs, and as such, it does not mention any specific software dependencies or versions. |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and approximation proofs, and as such, it does not describe any experimental setup details such as hyperparameters or training configurations. |