Learning Augmented Online Facility Location
- URL: http://arxiv.org/abs/2107.08277v1
- Date: Sat, 17 Jul 2021 16:44:27 GMT
- Title: Learning Augmented Online Facility Location
- Authors: Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, Nikolas
Patris
- Abstract summary: We present an online algorithm for Online Facility Location (OFL) that exploits potentially imperfect predictions on the locations of the optimal facilities.
We prove that the competitive ratio decreases smoothly from sublogarithmic in the number of demands to constant.
We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the error is optimal.
- Score: 11.401250502020503
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Following the research agenda initiated by Munoz & Vassilvitskii [1] and
Lykouris & Vassilvitskii [2] on learning-augmented online algorithms for
classical online optimization problems, in this work, we consider the Online
Facility Location problem under this framework. 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 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 smoothly from sublogarithmic in the number of
demands to constant, as the error, i.e., the total distance of the predicted
locations to the optimal facility locations, decreases towards zero. We
complement our analysis with a matching lower bound establishing that the
dependence of the algorithm's competitive ratio on the error is optimal, up to
constant factors. Finally, we evaluate our algorithm on real world data and
compare our learning augmented approach with the current best online algorithm
for the problem.
Related papers
- Handling Delayed Feedback in Distributed Online Optimization : A
Projection-Free Approach [1.9797215742507548]
Learning at the edges has become increasingly important as large quantities of data are continually generated locally.
We propose two projection-free algorithms for centralised and distributed settings in which they are carefully designed to achieve a regret bound of O(sqrtB) where B is the sum of delay.
We provide an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems.
arXiv Detail & Related papers (2024-02-03T10:43:22Z) - SpatialRank: Urban Event Ranking with NDCG Optimization on
Spatiotemporal Data [55.609946936979036]
We propose a novel spatial event ranking approach named SpatialRank.
We show that SpatialRank can effectively identify the top riskiest locations of crimes and traffic accidents.
arXiv Detail & Related papers (2023-09-30T06:20:21Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm.
We show FedBiO has complexity of $O(epsilon-1.5)$.
Our algorithms show superior performances compared to other baselines in numerical experiments.
arXiv Detail & Related papers (2022-05-03T16:40:22Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
We provide the first oracle-efficient, no-regret algorithms in this setting.
We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
arXiv Detail & Related papers (2022-02-09T19:22:34Z) - Learning-Augmented Dynamic Power Management with Multiple States via New
Ski Rental Bounds [38.80523710193321]
We study the online problem of minimizing power consumption in systems with multiple power-saving states.
An algorithm has to choose between power-saving states of different energy consumption and wake-up costs.
We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods.
arXiv Detail & Related papers (2021-10-25T17:14:20Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
We study the fundamental online $k$-server problem in a learning-augmented setting.
We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
arXiv Detail & Related papers (2021-03-02T11:04:33Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions.
The goal is to design algorithms that are both consistent and robust.
We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
arXiv Detail & Related papers (2020-10-22T04:51:01Z) - Online Learning of Facility Locations [21.451413948517228]
We provide a rigorous theoretical investigation of an online learning version of the Facility Location problem.
In our formulation, we are given a set of sites and an online sequence of user requests.
At each trial, the learner selects a subset of sites and then incurs a cost for each selected site and an additional cost which is the price of the user's connection to the nearest site in the selected subset.
arXiv Detail & Related papers (2020-07-06T15:04:53Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
Federated Learning (FL) has become a popular paradigm for learning from distributed data.
To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
arXiv Detail & Related papers (2020-05-22T23:07:42Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.