AG 1, AG 2, AG 3, AG 4, AG 5   Info

AG Audience

English

45 Minutes

Saarbrücken

Maria Minkoff

--email hidden

passcode not visible

logged in users only

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 distance is O(log^(7/2)n).