29 listopada 2016 10:15
[Seminarium ZOK]. Maciej Pacut: Online Balanced Repartitioning
Wtorek, 10:15, sala 310.
Abstract. I'll talk about an interesting model that is a generalization of caching. It can be viewed as an online variant of graph partitioning into clusters of the same size (the Balanced property). I'll provide a lower bound, an (up-to-constant) optimal algorithm for a restricted case, and an algorithm for a scenario with resource augmentation.
Joint work with Chen Avin, Andreas Loukas and Stefan Schmid from DISC 2016.