Parameterized Approximation Algorithms for K-center Clustering and Variants
Authors: Sayan Bandyapadhyay, Zachary Friggstad, Ramin Mousavi3895-3903
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a faster algorithm for small dimensions: roughly speaking an O (2O((1/ϵ)O(d) k1 1/d log k))-time (1 + ϵ)-approximation. In particular, the running time is roughly O (2O((1/ϵ)O(1) k log k)) in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of k-center, called Non-uniform k-center (NUk C), where we allow different radii clusters. NUk C is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2O(k log k)n2 time 3-approximation for NUk C in general metrics, and a 2O((k log k)/ϵ)dn time (1 + ϵ)-approximation for Euclidean NUk C. |
| Researcher Affiliation | Academia | Sayan Bandyapadhyay1, Zachary Friggstad2, Ramin Mousavi2 1 Department of Informatics, University of Bergen, Norway 2 Department of Computing Science, University of Alberta, Canada |
| Pseudocode | No | The paper describes algorithmic steps in prose (e.g., 'Preliminary Step: Reducing to a feasibility check', 'Step 1: Reducing the input size', 'The Algorithm.') but does not present them as structured pseudocode blocks or clearly labeled algorithm environments. |
| Open Source Code | No | The paper does not provide any links or statements about the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets, so no dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets, so no training/validation/test dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments requiring hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments, so it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |