Online Learning of Facility Locations

Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, Mark Herbster
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:1002-1050, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-pasteris21a, title = {Online Learning of Facility Locations}, author = {Pasteris, Stephen and He, Ting and Vitale, Fabio and Wang, Shiqiang and Herbster, Mark}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {1002--1050}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/pasteris21a/pasteris21a.pdf}, url = {https://proceedings.mlr.press/v132/pasteris21a.html}, 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.} }
Endnote
%0 Conference Paper %T Online Learning of Facility Locations %A Stephen Pasteris %A Ting He %A Fabio Vitale %A Shiqiang Wang %A Mark Herbster %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-pasteris21a %I PMLR %P 1002--1050 %U https://proceedings.mlr.press/v132/pasteris21a.html %V 132 %X 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.
APA
Pasteris, S., He, T., Vitale, F., Wang, S. & Herbster, M.. (2021). Online Learning of Facility Locations. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:1002-1050 Available from https://proceedings.mlr.press/v132/pasteris21a.html.

Related Material