Minimum-Cost Load-Balancing Partitions

Boris Aronov, Paz Carmi, Matthew J. Katz

    Research output: Contribution to journalArticle

    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 1,p m be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R 1,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 equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. In fact, we 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.

    Original languageEnglish (US)
    Pages (from-to)318-336
    Number of pages19
    JournalAlgorithmica (New York)
    Volume54
    Issue number3
    DOIs
    StatePublished - Jul 2009

    Keywords

    • Additive-weighted Voronoi diagram
    • Approximation algorithms
    • Fat partitions
    • Fatness
    • Geometric optimization
    • Load balancing

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Minimum-Cost Load-Balancing Partitions'. Together they form a unique fingerprint.

  • Cite this