On weighted rectilinear 2-center and 3-center problems (Q757236)

The authors consider the weighted rectilinear m-center optimization problem: given n demand points with positive weights, find m service points on the plane so as to minimize the maximum of the weighted rectilinear distances from the given demand points to their respective nearest service points. A number r is said to be feasible if there exists a set C of m service points such that the value of the objective function at C is less than or equal to r. For any \(r>0\), the weighted m-center decision problem consists in determining whether r is feasible. For \(m=2\) and \(m=3\), the authors propose O(n) algorithms for solving the corresponding decision problems. Then these algorithms are used to construct methods with time complexity O(n log n) for solving the m-center optimization problems corresponding to \(m=2\) and \(m=3\).