Nov. 29, 2016, 10:15 a.m.
[COG seminar]. Maciej Pacut: Online Balanced Repartitioning
Tuesday 10:15, room 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.