Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS
Authors: Sujoy Bhore, Devdan Dey, Satyam Singh
ICLR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first deterministic online algorithm with an optimal competitive ratio for intervals in R. Next, we give a randomized online algorithm with a near-optimal competitive ratio for axis-aligned boxes in Rd, for d 3. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in Rd, which may be of independent interest. Next, we focus on the continuous version of this problem (called online piercing set), where ranges of the set system are geometric concepts in Rd arriving in an online manner, but the universe is the entire ambient space, and the objective is to choose a small sample that intersects all the ranges. We advance this field by proposing asymptotically optimal competitive deterministic algorithms for boxes and ellipsoids in Rd, for any d N. Due to paucity, we move the proofs of several lemmas, theorems, and pseudo-codes in the Appendix. |
| Researcher Affiliation | Academia | Department of Computer Science and C-MIn DS, Indian Institute of Technology Bombay, Mumbai, India. Email: EMAIL. Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. Email: EMAIL. Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. Email: EMAIL. |
| Pseudocode | Yes | For a concise description of pseudo-code, see Algorithm 1 in Appendix C. For a concise description of the pseudo-code, see Algorithm 2 in Appendix C. Algorithm 1 Algorithm ALGO-INTERVAL for Construction of Online ε-Net N for arbitrary intervals. Algorithm 2 Construction of Online ε-Net N for axis-aligned rectangles. |
| Open Source Code | No | The paper does not provide any concrete access information for source code. |
| Open Datasets | No | The paper analyzes theoretical algorithms for geometric concepts (intervals, axis-aligned boxes, ellipsoids) and does not mention the use or availability of specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper focuses on theoretical algorithms and does not perform experiments requiring dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental methodology that would require hardware specifications. |
| Software Dependencies | No | The paper presents theoretical algorithms and does not provide details on specific software dependencies or their versions. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their competitive analysis, and does not include details on experimental setup or hyperparameters. |