2021/07/17 by Dimitris Fotakis, Fotakis, Dimitris, Evangelia Gergatsouli +6 · 1 citation
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2107.08277
openalex publication_date 2021/07/17 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number of demands n to constant as the so-called η1 error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases. E.g., our analysis implies that if for some ε > 0, η1 = OPT / nε, where OPT is the cost of the optimal solution, 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. Finally, we evaluate our algorithm on real world data and compare the performance of our learning-augmented approach against the performance of the best known algorithm for OFL without predictions.