2022/11/06 by Guillaume Ducoffe, Ducoffe, Guillaume
Business, Management and Accounting · Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management
paper · pdf · doi:10.48550/arxiv.2211.03146
openalex publication_date 2022/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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=(s1,s2,…,sp), the \em prioritized Voronoi diagram of G with respect to S is the partition of G in p subsets V1,V2,…,Vp so that, for every i with 1 ≤ i ≤ p, a vertex v is in Vi if and only if si is a closest vertex to v in S and there is no closest vertex to v in S within the subset \s1,s2,…,si-1\. For every i with 1 ≤ i ≤ p, the \em load of vertex si equals the sum of the costs of all vertices in Vi. 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 (\it 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 \cal O(nm) time on n-vertex m-edge graphs. We prove a matching time lower bound for the special case where m=n1+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.