Parameterized Approximation Schemes for Fair-Range Clustering
Authors: Zhen Zhang, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, Qilong Feng
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give (1 + ε)-approximation algorithms with fixed-parameter tractable running times for both problems, parameterized by the numbers of opened facilities and demographic labels. For Euclidean metrics, these are the first parameterized approximation schemes for the problems, improving upon the previously known O(1)-approximation ratios given by Thejaswi et al. (KDD 2022). |
| Researcher Affiliation | Academia | Zhen Zhang1,2, Xiaohong Chen1,2, , Limei Liu1,2, Jie Chen1,2, Junyu Huang3, Qilong Feng3,2 1National Key Laboratory Cultivation Base for Data Intelligence and Smart Society, Hunan University of Technology and Business, Changsha 410205, China 2Xiangjiang Laboratory, Changsha 410205, China 3School of Computer Science and Engineering, Central South University, Changsha 410083, China |
| Pseudocode | Yes | Algorithm 1: The data-reduction method; Algorithm 2: The algorithm for constructing annular search spaces; Algorithm 3: The algorithm for low-dimensional weighted instances; Algorithm 4: The algorithm in high-dimensional spaces |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code availability for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies with datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies with dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software dependencies with version numbers for experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setup details like hyperparameters or training settings. |