Optimal Coresets for Low-Dimensional Geometric Median
Authors: Peyman Afshani, Chris Schwiegelshohn
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate coresets for approximating the cost with respect to median queries. In this problem, we are given a set of points P Rd and median queries are P p P p c for any point c Rd. Our goal is to compute a small weighted summary S P such that the cost of any median query is approximated within a multiplicative (1 ε) factor. We provide matching upper and lower bounds on the number of points contained in S of the order Θ ε d/(d+1) . |
| Researcher Affiliation | Academia | 1Department of Computer Science, Aarhus University, Denmark. |
| Pseudocode | No | The paper describes algorithms and constructions conceptually and mathematically but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statements about making its source code publicly available, nor does it provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. Therefore, it does not provide information about training dataset splits. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets. Therefore, it does not provide information about validation dataset splits. |
| Hardware Specification | No | The paper does not provide any specific details about hardware used for computational experiments, as it is a theoretical work. |
| Software Dependencies | No | The paper does not list any specific software dependencies with version numbers, as it focuses on theoretical proofs and algorithms rather than implementation details. |
| Experiment Setup | No | The paper focuses on theoretical contributions and does not describe an experimental setup with hyperparameters or training configurations. |