Fall 2017

Online Algorithms via Projections

Tuesday, December 11th, 2018 10:15 am10:45 am

Add to Calendar


Anupam Gupta (Carnegie Mellon University)

We consider the $k$-server problem on trees and HSTs. We give an algorithm based on Bregman projections, whose competitive ratio matches those in recent results of Bubeck et al. (STOC 2018). Joint work with Niv Buchbinder, Marco Molinaro, and Seffi Naor.