In this paper, 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 appear 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 @math . The problem has not been studied before. We present an O(|T|+M ^2 M) time algorithm for the problem, 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. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.
Very recently, Li and Huang @cite_6 considered the same @math -center problem under the same uncertain model as ours but in the Euclidean space, and they gave an approximation algorithm. Facility location problems in other uncertain models have also been considered. For example, L "o ffler and van Kreveld @cite_39 gave algorithms for computing the smallest enclosing circle for imprecise points each of which is contained in a planar region (e.g., a circle or a square). J @cite_31 studied the problem of computing the distribution of the radius of the smallest enclosing circle for uncertain points each of which has multiple locations in the plane. de @cite_0 proposed algorithms for dynamically maintaining Euclidean @math -centers for a set of moving points in the plane (the moving points are considered uncertain). See also the problems for minimizing the maximum regret, e.g., @cite_7 @cite_9 @cite_36 .
@cite_7 @cite_36 @cite_9 @cite_6 @cite_39 @cite_0 @cite_31
2030028156 1982820819 2018274124 2007553965 2009033070 1547243772
We consider single facility location problems (1-median and weighted 1-center) on a plane with uncertain weights and coordinates of customers (demand points). Specifically, for each customer, only interval estimates for its weight and coordinates are known. It is required to find a ''minmax regret'' location, i.e. to minimize the worst-case loss in the objective function value that may occur because the decision is made without knowing the exact values of customers' weights and coordinates that will get realized. We present an O(n^2log^2n) algorithm for the interval data minmax regret rectilinear 1-median problem and an O(nlogn) algorithm for the interval data minmax regret rectilinear weighted 1-center problem. For the case of Euclidean distances, we consider uncertainty only in customers' weights. We discuss possibilities of solving approximately the minmax regret Euclidean 1-median problem, and present an O(n^22^@a^(^n^)log^2n) algorithm for solving the minmax regret Euclidean weighted 1-center problem, where @a(n) is the inverse Ackermann function. Let P be an undirected path graph of n vertices. Each edge of P has a positive length and a constant capacity. Every vertex has a nonnegative supply, which is an unknown value but is known to be in a given interval. The goal is to find a point on P to build a facility and move all vertex supplies to the facility such that the maximum regret is minimized. The previous best algorithm solves the problem in O(nlog2n) time and O(nlogn) space. In this paper, we present an O(nlogn) time and O(n) space algorithm, and our approach is based on new observations and algorithmic techniques. Abstract We consider the weighted p-center problem on a transportation network with uncertain weights of nodes. Specifically, for each node, an interval estimate of its weight is known. The objective is to find the ‘minimax regret’ solution i.e. to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We discuss properties of the problem and show that the problem can be solved by means of solving (n + 1) regular weighted p-center problems. This leads to polynomial algorithms for the cases where the regular weighted p-center problem can be solved in polynomial time, e.g. for the case of a tree network, and for the case of a general network with p = 1. Imprecision of input data is one of the main obstacles that prevent geometric algorithms from being used in practice. We model an imprecise point by a region in which the point must lie. Given a set of imprecise points, we study computing the largest and smallest possible values of various basic geometric measures on point sets, such as the diameter, width, closest pair, smallest enclosing circle, and smallest enclosing bounding box. We give efficient algorithms for most of these problems, and identify the hardness of others. We study two versions of the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound d_ max on the maximum displacement of any point within one time step. We show how to maintain the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+e)-approximation of the optimal 2-center. In many cases---namely when the distance between the centers of the disks is relatively large or relatively small---the solution we maintain is actually optimal. We also present results for the case where the maximum speed of the centers is bounded. We describe a simple scheme to maintain a 2-approximation of the rectilinear 2-center, and we provide a scheme which gives a better approximation factor depending on several parameters of the point set and the maximum allowed displacement of the centers. The latter result can be used to obtain a 2.29-approximation for the Euclidean 2-center; this is an improvement over the previously best known bound of 8 π approx 2.55. These algorithms run in amortized sub-linear time per time step, as before under certain assumptions on the distribution. We study computing with indecisive point sets. Such points have spatial uncertainty where the true location is one of a finite number of possible locations. This data arises from probing distributions a few times or when the location is one of a few locations from a known database. In particular, we study computing distributions of geometric functions such as the radius of the smallest enclosing ball and the diameter. Surprisingly, we can compute the distribution of the radius of the smallest enclosing ball exactly in polynomial time, but computing the same distribution for the diameter is #P-hard. We generalize our polynomial-time algorithm to all LP-type problems. We also utilize our indecisive framework to deterministically and approximately compute on a more general class of uncertain data where the location of each point is given by a probability distribution.