Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
In this work we consider an online learning problem, called Online k-Clustering with Moving Costs, at which a learner maintains a set of k facilities over T rounds so as to minimize the connection cost of an adversarially selected sequence of clients. The learner is informed on the positions of the clients at each round t only after its facility-selection and can use this information to update its decision in the next round. However, updating the facility positions comes with an additional moving cost based on the moving distance of the facilities. We present the first O(log n)-regret polynomial-time online learning algorithm guaranteeing that the overall cost (connection + moving) is at most O(log n) times the time-averaged connection cost of the best fixed solution. Our work improves on the recent result of Fotakis et al. [31] establishing O(k)-regret guarantees only on the connection cost.
Anastasia Ailamaki, Viktor Sanca, Eleni Zapridou, Stefan Igescu
Robert West, Maxime Jean Julien Peyrard, Marija Sakota