Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants
Authors: Xianrun Chen, Dachuan Xu, Yicheng Xu, Yong Zhang
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a general technical framework to overcome the challenge posed by varying radii in So R, which yields fixed-parameter tractable (fpt) algorithms with respect to k (i.e., whose running time is f(k)ploy(n) for some f). Our framework is versatile and obtains fpt approximation algorithms with constant approximation ratios for So R as well as its variants in general metrics, such as Fair So R and Matroid So R, which significantly improve the previous results. Our main result is a unified framework that returns (2+ε)-approximation for So R and (3+ε)-approximation for both Fair So R and Mat So R respectively that all run in times of 2k log(k/ε)n O(1). |
| Researcher Affiliation | Academia | 1 Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China 2 University of Chinese Academy of Sciences, Beijing, China 3 Beijing University of Technology, Beijing, China |
| Pseudocode | Yes | Algorithm 1: Iterative covering. Algorithm 2: Fair exchange via matching. Algorithm 3: Exchange via matroid intersetcion. |
| Open Source Code | No | The paper does not contain any statement about releasing source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and analysis. It does not use or reference any specific datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper. No dataset splits (e.g., training, validation, test) are mentioned or discussed, as it does not involve empirical validation. |
| Hardware Specification | No | This is a theoretical paper focused on algorithm design and analysis; therefore, no specific hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | This is a theoretical paper. It does not list any specific software dependencies with version numbers (e.g., libraries, frameworks, or solvers). |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and analysis, and thus does not include details on experimental setup such as hyperparameters or training settings. |