Can I read Tight Bounds for Online Graph Partitioning on EtoBox?

Tight Bounds for Online Graph Partitioning by Monika Henzinger; Stefan Neumann; Harald Räcke; Stefan Schmid is a book available to read on EtoBox.

What is Tight Bounds for Online Graph Partitioning about?

We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of servers, where servers have capacity k and we assume that the graph has • k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than k for constant > 0.Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT.The problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as unionfind data structures.Our main contribution is a polynomial-time randomized algorithm, that is asym

Author

Monika Henzinger; Stefan Neumann; Harald Räcke; Stefan Schmid

Publisher

Society for Industrial and Applied Mathematics

Published

2021

Language

EN