Minimum-cost load-balancing partitions

ABSTRACT

We consider the problem of balancing the load among several service-providing facilities, while keeping the total cost low. Let D be the underlying demand region, and let p₁, …, p_m be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R₁, …, R_m, so that region R_i is served by facility p_i, and the average distance between a point q in D and the facility that serves q is minimal.We present constant-factor approximation algorithms for this problem, with the additional requirement that the resulting regions must be convex. As an intermediate result we show how to partition a convex polygon into m=2^k equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. We also prove that our partition is, up to a constant factor, the best one can get if one's goal is to maximize the fatness of the least fat subregion.We also discuss the structure of the optimal partition for the aforementioned load balancing problem: indeed, we argue that it is always induced by an additive-weighted Voronoi diagram for an appropriate choice of weights.

REFERENCES

• 1: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 2: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• 3: F. Aurenhammer, F. Hoffmann, and B. Aronov. Minkowski-type theorems and least-squares clustering. Algorithmica, 20(1) (1998), 61--76.
• 4: M. de Berg, M.J. Katz, A.F. van der Stappen, and J. Vleugels. Realistic input models for geometric algorithms. Algorithmica, 34(1) (2002), 81--97.
• 5: P. Carmi. Approximation Algorithms for Geometric Problems in Wireless Communication Networks. Ph.D. Thesis, Ben-Gurion University, March 2006.
• 6: P. Carmi, S. Dolev, S. Har-Peled, M.J. Katz, and M. Segal. Geographic quorum system approximations. Algorithmica, 41(4) (2005), 233--244.
• 7: P. Carmi, S. Har-Peled, and M.J. Katz, On the Fermat-Weber center of a convex object. Comput. Geom. Theory Appl., 32(3) (2005), 188--195.
• 8: Julia Chuzhoy , Yuval Rabani, Approximating k-median with non-uniform capacities, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Sándor P. Fekete , Joseph S. B. Mitchell , Karin Beurer, On the Continuous Fermat-Weber Problem, Operations Research, v.53 n.1, p.61-76, January 2005 [doi>10.1287/opre.1040.0137]
• 10: H.W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1955), 83--97.
• 11: D.B. West. Introduction to Graph Theory. Second edition, Prentice Hall, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
additive-weighted Voronoi diagrams, approximation algorithms, fat partitions, fatness, geometric optimization, load balancing