Given a convex polygon @math with @math vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover @math . We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius @math satisfying @math using @math space, where @math is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by @math , maintaining the time complexity of the algorithm to @math , and using @math extra space in addition to the space required for storing the input.
In the streaming model, @cite_11 and Guha @cite_2 have designed a ( @math )-approximation algorithm for the @math -center problem of a point set in @math using @math space. For the 1-center problem, Agarwal and Sharathkumar @cite_7 suggested a @math -factor approximation algorithm using @math space. The approximation factor was later improved to @math by Chan and Pathak @cite_18 . Recently, Kim and Ahn @cite_3 proposed a ( @math )-approximation algorithm for the two-center problem of a point set in @math . It uses @math space and update time where insertion and deletion of the points in the set are allowable. To the best of our knowledge, there is no approximation result for the two-center problem for a convex polygon under the streaming model.
@cite_18 @cite_7 @cite_3 @cite_2 @cite_11
2055900608 2215609590 2295466155 2950256099
At [email protected]?10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1+3) [email protected] 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1+2) 2 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(dlogn) expected amortized time per insertion deletion. Abstract In the k -center problem for streaming points in d -dimensional metric space, input points are given in a data stream and the goal is to find the k smallest congruent balls whose union covers all input points by examining them. In the single-pass streaming model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. In this paper, we present a single-pass, ( 1.8 + e ) -factor, O ( d e ) -space data stream algorithm for the Euclidean 2-center problem for any d ≥ 1 . This is the first result with an approximation factor below 2 using O ( d e ) space for any d . Our algorithm naturally extends to the Euclidean k -center problem with k > 2 . We present a single-pass ( 1.8 + e ) -factor data stream algorithm for the Euclidean k -center problem for any d ≥ 1 , which uses O ( 2 k ( k + 3 ) ! d e ) space and O ( 2 k ( k + 2 ) ! d e ) update time. We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore O(√n) approximation with polylogarithmic space in an n vertex graph and a constant approximation with Ω(n) space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in n. Our algorithm is obtained by effecting a streaming implementation of a simple "local" algorithm that we design for this problem. The local algorithm produces a O(k · n1 k) approximation to the size of a maximum matching by exploring the radius k neighborhoods of vertices, for any parameter k. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for k = Ω(log n log log n). Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems. We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass @math -approximation streaming algorithm can be easily obtained with space @math , where @math denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space @math is granted, for every @math . Specifically, for every @math , we show that in the one-pass turnstile streaming model, in order to compute a @math -approximation, space @math is required for constant error randomized algorithms, and, up to logarithmic factors, space @math is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest.