Advertisement
Published in:
2005 | OriginalPaper | Chapter
From Balls and Bins to Points and Vertices
Authors : Ralf Klasing, Zvi Lotker, Alfredo Navarra, Stephane Perennes
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 a bijection from the points to the vertices that minimizes 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 graphs, we prove the #
P
-hardness of the problem and that the maximum relocation distance is
$O(\sqrt{n})$
with high probability. We also present a Fully Polynomial Randomized Approximation Scheme when the input graph admits a polynomial-size family of witness cuts while for trees we provide a 2-approximation algorithm.