From Balls and Bins to Points and Vertices

Authors

  • Ralf Klasing LaBRI - Université Bordeaux
  • Zvi Lotker Ben Gurion University
  • Alfredo Navarra Università degli Studi di Perugia
  • Stéphane Pérennes I3S-CNRS/INRIA/University of Nice

Abstract

Given a graph G = (V, E) with |V| = n, we consider the following problem. Place m = 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 and in the case m ≤ n, we prove the #P -hardness of the problem and that the maximum relocation distance is O(√n) with high probability. We 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. Many applications concern the variation in which m = (1 − ǫ)n for some 0 < ǫ < 1. We provide several bounds for the maximum relocation distance according to different graph topologies.

Downloads

Published

2009-09-16

How to Cite

Klasing, R., Lotker, Z., Navarra, A., & Pérennes, S. (2009). From Balls and Bins to Points and Vertices. Algorithmic Operations Research, 4(2), Pages 133 – 143. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/4668

Issue

Vol. 4 No. 2 (2009)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.