Random Cuts are Optimal for Explainable k-Medians
Authors: Konstantin Makarychev, Liren Shan
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the RANDOMCOORDINATECUT algorithm gives the optimal competitive ratio for explainable k-medians in ℓ1. ... We provide a tight analysis of the algorithm and prove that its competitive ratio is upper bounded by 2 ln k + 2. |
| Researcher Affiliation | Academia | Konstantin Makarychev Northwestern University Liren Shan TTIC |
| Pseudocode | Yes | Figure 2: RANDOMCOORDINATECUT algorithm |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-source code of the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not mention any specific datasets for training or provide access information for any dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe any dataset splits (training, validation, or testing). |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware used for any experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training settings. |