Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of 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