The Power of Uniform Sampling for k-Median
Authors: Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments Our experiments focus on validating the performance of running an algorithm for k-MEDIAN (instead of (k, β)-MEDIAN) on top of the uniform S, since it is arguably the most natural approach and is likely to be used in practice. Our experiments were conducted on various real datasets of different types of metric spaces including Euclidean Rd and shortest-path metrics. We find that the solution returned by the k-MEDIAN algorithm is fairly balanced, which effectively enforces the balancedness constraint of (k, β)-MEDIAN. |
| Researcher Affiliation | Academia | 1State Key Laboratory of Novel Software Technology, Nanjing University, Jiangsu, China 2Center on Frontiers of Computing Studies, Peking University, Beijing, China. |
| Pseudocode | No | The paper describes algorithms and methods but does not include any clearly labeled pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide any links to open-source code for the methodology described. |
| Open Datasets | Yes | Our experiments are conducted on 3 real datasets: Twitter (Chan et al., 2018), Census1990 (Meek et al., 1990) and NY (Open Street Map contributors, 2017). |
| Dataset Splits | No | The paper mentions taking 'm uniform samples S from the dataset with varying m' but does not specify training, validation, or test dataset splits or how data was partitioned for cross-validation. |
| Hardware Specification | Yes | All experiments are conducted on a PC with Intel Core i7 CPU and 16 GB memory |
| Software Dependencies | No | The paper states 'algorithms are implemented in C++ 11'. While 'C++ 11' specifies a language standard version, it does not include version numbers for any specific libraries, frameworks, or compilers, which are typically needed for full reproducibility. |
| Experiment Setup | No | The paper mentions running a 'local search algorithm (Arya et al., 2001)' but does not specify any hyperparameters or system-level training settings for this algorithm. |