Date:
Thu, 01/02/202410:30-11:30
Location:
Sprinzak 29
The graphical balls-into-bins process is an overseen process in which balls are assigned one by one to the vertices of a d-regular graph G. At each time step an edge of G is chosen uniformly at random, and the overseer must assign a ball to either of the two endpoints of this edge. The classical 2-choice process corresponds to the case of G=Kn. The purpose of the overseer is that the allocation will be as well balanced as possible, namely that the load difference between the most loaded and the least loaded bins will be minimal, known as the allocation “gap”.
Previously it was thought that for constant d, for certain graphs the gap has to be polynomially big. We show that this is not the case. For any k(n)-edge-connected, d(n)-regular graph on n vertices, and any number of balls, we give an allocation strategy that, with high probability, ensures a gap of O((d/k) log4n loglogn), between the load of any two bins. A not-too-difficult lower bound of Ω((d/k) + logn) on the gap achievable by any allocation strategy implies that our strategy achieves the optimal gap, up to polylogarithmic factors, for every graph G.
A key idea is to relate the problem of designing a good allocation strategy to that of finding suitable multi-commodity flows on G. To this end, we consider Räcke’s cut-based decomposition tree and define certain orthogonal flows on it.
Joint work with Nikhil Bansal from the University of Michigan
Previously it was thought that for constant d, for certain graphs the gap has to be polynomially big. We show that this is not the case. For any k(n)-edge-connected, d(n)-regular graph on n vertices, and any number of balls, we give an allocation strategy that, with high probability, ensures a gap of O((d/k) log4n loglogn), between the load of any two bins. A not-too-difficult lower bound of Ω((d/k) + logn) on the gap achievable by any allocation strategy implies that our strategy achieves the optimal gap, up to polylogarithmic factors, for every graph G.
A key idea is to relate the problem of designing a good allocation strategy to that of finding suitable multi-commodity flows on G. To this end, we consider Räcke’s cut-based decomposition tree and define certain orthogonal flows on it.
Joint work with Nikhil Bansal from the University of Michigan