Improved Bounds for Online Facility Location with Predictions
Authors: Dimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis, Nikolas Patris, Thanos Tolias
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that the competitive ratio decreases from sublogarithmic in the number of demands n to constant as the total prediction error η1... E.g., our analysis implies that if for some ε > 0, η1 = OPT/nε, where OPT is the optimal cost, the competitive ratio becomes O(1/ε). We complement our analysis with a matching lower bound establishing that the dependence of the algorithm s competitive ratio on the η1 error is optimal, up to constant factors. |
| Researcher Affiliation | Academia | 1National Technical University of Athens, Greece 2Archimedes/Athena RC, Greece 3University of Wisconsin Madison, WI, USA 4Georgia Institute of Technology, Atlanta, GA, USA 5Nanyang Technological University, Singapore 6University of California, Irvine, CA, USA EMAIL, EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: PREDOFL: OFL with Predictions Input: Demand-prediction pairs (v1, p1), . . . , (vn, pn) 1: F = {set of open facilities} 2: for each demand-prediction pair (vt, pt) do 3: With probability min{1, d(F, pt)/f}: F = F {pt} {new facility opens at pt} 4: Assign vt to nearest facility in F with cost d(F, vt) 5: end for |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating the availability of open-source code for the methodology described. It refers to an arXiv preprint for proofs and technical details, but not code. |
| Open Datasets | No | The paper presents theoretical algorithms and competitive ratio analysis for Online Facility Location with predictions in a metric space. It does not use or evaluate on any specific public or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, no dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design and mathematical proofs. It does not describe any experimental setup or specify hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software implementations, libraries, or dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical, presenting algorithms and their competitive analysis. It does not include an experimental section, thus no experimental setup details or hyperparameters are provided. |