We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in O(n log 2 n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively. In this paper, we study a classical k-center problem in trees. Let T be a tree of n vertices. Each edge e(u, v) connecting two vertices u and v has a positive length d(u, v), and we consider the edge as a line segment of length d(u, v) so that we can talk about "points" on the edge. For any two points p and q of T , there is a unique path in T from p to q, denoted by π(p, q), and by slightly abusing the notation, we use d(p, q) to denote the length of π(p, q). Each vertex v of T is associated with a weight w(v) ≥ 0. The k-center problem is to compute a set Q of k points on T , called centers, such that the maximum weighted distance from all vertices of T to their closest centers is minimized, or formally, the value max v∈V (T ) min q∈Q {w(v) · d(v, q)} is minimized, where V (T ) is the vertex set of T . Note that each center can be in the interior of an edge of T . Kariv and Hakimi [20] first gave an O(n 2 log n) time algorithm for the problem. Jeger and Kariv [19] proposed an O(kn log n) time algorithm. Megiddo and Tamir [25] solved the problem in O(n log 2 n log log n) time, and the running time of their algorithm can be reduced to O(n log 2 n) by applying Cole's parametric search [12]. Some progress has been made very recently by Banik et al. [3], where an O(n log n+k log 2 n log(n/k))-time algorithm and another O(n log n+k 2 log 2 (n/k))time algorithm were given, and both algorithms favor small values of k. Since Megiddo and Tamir's work [25] , it has been open whether the problem can be solved in O(n log n) time. In this paper, we settle this three-decade long open problem affirmatively by presenting an O(n log n)-time algorithm. Note that the previous O(n log 2 n)-time algorithm [12, 25] and the first algorithm in [3] both rely on Cole's parametric search, which involves a large constant in the time complexity due to the AKS sorting network [2]. Our algorithm, however, avoids Cole's parametric search. If each center is required to be located a vertex of T , then we call it the discrete case. The previously best-known algorithm for this case runs in O(n log 2 n) time [26] . Our techniques also solve the discrete case in O(n log n) time. Many variations of the k-center problem have been studied. If k = 1, then the problem is solvable in O(n) time [23] . If T is a path, the k-center problem was already solved in O(n log n) time [9, 12, 25] , and Bhattacharya and Shi [4] also gave an algorithm whose running time is linear in n but exponential in k. For the unweighted case where the vertices of T have the same weight, an O(n 2 log n)-time algorithm was given in [8] for the k-center problem. Later, Megiddo et al. [26] solved the problem in O(n log 2 n) time, and the algorithm was improved to O(n log n) time [17] . Finally, Frederickson [16] solved the problem in O(n) time. The above four papers also solve the discrete case and the following problem version in the same running times: All points of T are considered as demand points and the centers are required to be at vertices of T . Further, if all points of T are demand points and centers can be any points of T , Megiddo and Tamir solved the problem in O(n log 3 n) time [25] , and the running time can be reduced to O(n log 2 n) by applying Cole's parametric search [12]. As related problems, Frederickson [15] presented O(n)-time algorithms for the following tree partitioning problems: remove k edges from T such that the maximum (resp., minimum) total weight of all connected subtrees is minimized (resp., maximized). Finding k centers in a general graph is NP-hard [20]. The geometric version of the problem in the plane is also NP-hard [24], i.e., finding k centers for n demanding points in the plane. Some special cases, however, are solvable in polynomial time. For example, if k = 1, then the problem can be solved in O(n) time [23] , and if k = 2, it can be solved in O(n log 2 n log 2 log n) time [7] (also refer to [1] for a faster randomized algorithm). If we require all centers to be on a given line, then the problem of finding k centers can be solved in polynomial time [5, 21, 27] . Recently, problems on uncertain data have been studied extensively and some k-center problem variations on uncertain data were also considered, e.g., [13, 18, 28, 29, 30, 31] .
Wang and Zhang REF recently gave an O(n log n) time algorithm for the problem.
An O(n\log n)-Time Algorithm for the k-Center Problem in Trees
ArXiv
ArXiv
Computer Science Mathematics