• Calendar

January 6, Thursday
12:00 – 14:00

Given a graph $G=(V,E)$ with $|V|=n$, we consider the following problem: place $n$ points on the vertices of $G$ independently and uniformly at random. Once the points are placed, relocate them using bijection from the points to the vertices that minimize the maximum distance between the random place of the points and their target vertices.

We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points).

For general graph we prove that the maximum relocation distance is $O(\sqrt{n})$ w.h.p., for grid we prove that the maximum relocation

This is joint work with Ralf Klasing, Alfredo Navarra, St'ephane P'erennes.