Locating Centers on a Tree with Discontinuous Supply and Demand Regions

Consider a tree T = (N, E) with “supply” and “demand” regions Σ and Δ, each composed of a finite number of disjoint, closed and connected subregions of T, some of which may possibly consist of just one point. Given an integer p, we seek a collection of p “centers” x₁, …, x_p ∈ Σ, which minimize the expression max_y∈δ min_i=1,…,pd(y, x_i). We present a polynomial algorithm for this problem. Its running time is bounded by O(n log²n) if either Δ or Σ is discrete, and by O(n min|p log²n,n log p|) if both sets contain at least one full edge.