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 @math time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in @math time. In this paper, we present an @math time algorithm for the problem and thus settle the open problem affirmatively.
 For a set Pof npoints in i¾?2, the Euclidean 2-center problem computes a pair of congruent disks of the minimal radius that cover P. We extend this to the (2,k)-center problem where we compute the minimal radius pair of congruent disks to cover ni¾? kpoints of P. We present a randomized algorithm with O(nk7log3n) expected running time for the (2,k)-center problem. We also study the (p,k)-center problem in i¾?2under the i¾? i¾? -metric. We give solutions for p= 4 in O(kO(1)nlogn) time and for p= 5 in O(kO(1)nlog5n) time. In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line l is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of l is fixed, we give an O(n2log2 n)-time algorithm. When l is an arbitrary line, we give a randomized algorithm with expected running time O(n4log2 n). Then we present (1+e)-approximation algorithms for these three problems. When we denote T(k, e) = (k e2+(k e) log k) log(1 e), these algorithms run in O(n log k + T(k, e)) time, O(n log k + T(k, e) e) time, and O(n log k + T(k, e) e2) time, respectively. For k = O(n1 3 log n), we also give randomized algorithms with expected running times O(n + (k e2) log(1 e)), O(n+(k e3) log(1 e)), and O(n + (k e4) log(1 e)), respectively. Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows: We consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set ( P ) of n (weighted) demand points, and the location of each demand point (P_i P ) is uncertain but is known to be in one of (m_i ) points on T each associated with a probability. Given a covering range ( ), the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point (P_i P ), the expected distance from (P_i ) to at least one center is no more than ( ). The problem has not been studied before. We present an (O(|T|+M ^2 M) ) time algorithm, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of ( P ), i.e., (M= _ P_i P m_i ).  The (weighted) k-median, k-means, and k-center problems in the plane are known to be NP-hard. In this paper, we study these problems with an additional constraint that requires the sought k facilities to be on a given line. We present efficient algorithms for various distance measures such as L1,L2,L∞. We assume that all n weighted points are given sorted by their projections on the given line. For k-median, our algorithms for L1 and L∞ metrics run in O(min nk,nklog nlog n,n2O(log klog log n)log n ) time and O(min nklog n,nklog nlog2n,n2O(log klog log n)log2n ) time, respectively. For k-means, which is defined only on the squared L2 distance, we give an O(min nk,nklog n,n2O(log klog log n) ) time algorithm. For k-center, our algorithms run in O(nlog n) time for all three metrics, and in O(n) time for the unweighted version under L1 and L∞ metrics. While our results for the k-center problem are optimal, the results for the k-median problem almost match the best algorithms for the corresponding one-dimensio... Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k-center problem on one-dimensional uncertain data. The input is a set P of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (i.e., a histogram). The goal is to find a set Q of k points on the line to minimize the maximum expected distance from the uncertain points of P to their expected closest points in Q. We present efficient algorithms for this uncertain k-center problem and their running times almost match those for the "deterministic" k-center problem. There is an increasing quantity of data with uncertainty arising from applications such as sensor network measurements, record linkage, and as output of mining algorithms. This uncertainty is typically formalized as probability density functions over tuple values. Beyond storing and processing such data in a DBMS, it is necessary to perform other data analysis tasks such as data mining. We study the core mining problem of clustering on uncertain data, and define appropriate natural generalizations of standard clustering optimization criteria. Two variations arise, depending on whether a point is automatically associated with its optimal center, or whether it must be assigned to a fixed cluster no matter where it is actually located. For uncertain versions of k-means and k-median, we show reductions to their corresponding weighted versions on data with no uncertainties. These are simple in the unassigned case, but require some care for the assigned version. Our most interesting results are for uncertain k-center, which generalizes both traditional k-center and k-median objectives. We show a variety of bicriteria approximation algorithms. One picks O(ke--1log2n) centers and achieves a (1 + e) approximation to the best uncertain k-centers. Another picks 2k centers and achieves a constant factor approximation. Collectively, these results are the first known guaranteed approximation algorithms for the problems of clustering uncertain data. We consider the one-dimensional one-center problem on uncertain data. We are given a set P of n (weighted) uncertain points on a real line L and each uncertain point is specified by a probability density function that is a piecewise-uniform function (i.e., a histogram). The goal is to find a point c (the center) on L such that the maximum expected distance from c to all uncertain points of P is minimized. We present a linear-time algorithm for this problem. Problems of finding p-centers and dominating sets of radius r in networks are discussed in this paper. Let n be the number of vertices and @math be the number of edges of a network. With the assumption that the distance-matrix of the network is available, we design an @math algorithm for finding an absolute 1-center of a vertex-weighted network and an @math algorithm for finding an absolute 1-center of a vertex-unweighted network (the problem of finding a vertex 1-center of a network is trivial). We show that the problem of finding a (vertex or absolute) p-center (for @math ) of a (vertex-weighted or vertex-unweighted) network, and the problem of finding a dominating set of radius r are @math -hard even in the case where the network has a simple structure (e.g., a planar graph of maximum vertex degree 3). However, we describe an algorithm of complexity @math (respectively, $ O[| E |^p n^ 2p - 1... Abstract This paper considers the planar Euclidean two-center problem: given a planar n-point set S, find two congruent circular disks of the smallest radius covering S. The main result is a deterministic algorithm with running time O(nlog2nlog2logn), improving the previous O(nlog9n) bound of Sharir and almost matching the randomized O(nlog2n) bound of Eppstein. If a point in the intersection of the two disks is given, then we can solve the problem in O(nlogn) time with high probability. Given n demand points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize the maximum distance from a demand point to its respective nearest supply point. The p-median problem is to minimize the sum of distances from demand points to their respective nearest supply points. We prove that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, we prove that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability. Uncertain data has been very common in many applications. In this paper, we consider the one-center problem for uncertain data on tree networks. In this problem, we are given a tree T and n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to find a point @math xź on T such that the maximum (weighted) expected distance from @math xź to all uncertain points is minimized. To the best of our knowledge, this problem has not been studied before. We propose a refined prune-and-search technique that solves the problem in linear time.