26 maja 2026 10:15
[Seminarium ZOK] Agnieszka Tatarczuk: Online Bisection with Ring Demands
The online bisection problem requires maintaining a dynamic partition of n nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in different clusters, the algorithm pays unit cost. After each request, the algorithm may migrate nodes between clusters at unit cost per node. This problem models datacenter resource allocation where virtual machines must be assigned to servers, balancing communication costs against migration overhead. We study the variant where requests are restricted to edges of a ring network, an abstraction of ring-allreduce patterns in distributed machine learning. Despite this restriction, the problem remains challenging with an \Omega(n) deterministic lower bound. We present a randomized algorithm
achieving O(k^3 · log^2 n) competitive ratio using resource augmentation that allows clusters of size at most (3/4 + 1/(2k)) · n.
Joint work with Mateusz Basiak, Marcin Bieńkowski and Guy Even.
ArXiv link: https://arxiv.org/abs/2602.10337