Pasteris, S;
He, T;
Vitale, F;
Wang, S;
Herbster, M;
(2021)
Online Learning of Facility Locations.
In:
Proceedings of the 32nd International Conference on Algorithmic Learning Theory.
(pp. pp. 1002-1050).
PMLR 132
Preview |
Text
pasteris21a.pdf - Published Version Download (421kB) | Preview |
Abstract
In this paper, we provide a rigorous theoretical investigation of an online learning version of the Facility Location problem which is motivated by emerging problems in real-world applications. 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. The problem may be solved by an application of the well-known Hedge algorithm. This would, however, require time and space exponential in the number of the given sites, which motivates our design of a novel quasi-linear time algorithm for this problem, with good theoretical guarantees on its performance.
| Type: | Proceedings paper |
|---|---|
| Title: | Online Learning of Facility Locations |
| Event: | 32nd International Conference on Algorithmic Learning Theory |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.mlr.press/v132/pasteris21a.htm... |
| Language: | English |
| Additional information: | This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Machine learning, Online optimisation, Facility location problem |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10172868 |
Archive Staff Only
 |
View Item |
