Balancing graph Voronoi diagrams with one more vertex
share
Let G=(V,E) be a graph with unit-length edges and nonnegative costs assigned to its vertices. Being given a list of pairwise different vertices S=(s_1,s_2,…,s_p), the prioritized Voronoi diagram of G with respect to S is the partition of G in p subsets V_1,V_2,…,V_p so that, for every i with 1 ≤ i ≤ p, a vertex v is in V_i if and only if s_i is a closest vertex to v in S and there is no closest vertex to v in S within the subset {s_1,s_2,…,s_i-1}. For every i with 1 ≤ i ≤ p, the load of vertex s_i equals the sum of the costs of all vertices in V_i. The load of S equals the maximum load of a vertex in S. We study the problem of adding one more vertex v at the end of S in order to minimize the load. This problem occurs in the context of optimally locating a new service facility (e.g., a school or a hospital) while taking into account already existing facilities, and with the goal of minimizing the maximum congestion at a site. There is a brute-force algorithm for solving this problem in O(nm) time on n-vertex m-edge graphs. We prove a matching time lower bound for the special case where m=n^1+o(1) and p=1, assuming the so called Hitting Set Conjecture of Abboud et al. On the positive side, we present simple linear-time algorithms for this problem on cliques, paths and cycles, and almost linear-time algorithms for trees, proper interval graphs and (assuming p to be a constant) bounded-treewidth graphs.
READ FULL TEXT