Bureaucrats, editor, Administrators
373
edits
Changes
→Abstract
Line 16:
Line 16:
1- the cost of solving the facility location problem for each P_i is small (which means that for each P_i one needs to open only a small, polylogarithmic number of facilities),
1- the cost of solving the facility location problem for each P_i is small (which means that for each P_i one needs to open only a small, polylogarithmic number of facilities),
− 2- sum_i opt(P_i) \le (1+eps) opt(P), where for a point set P, opt(P) denotes the cost of an optimal solution for P.
2- sum_i opt(P_i) \le (1+eps) opt(P), where for a point set P, opt(P) denotes the cost of an optimal solution for P.
Line 23:
Line 21:
1- A (1+eps)-approximation algorithm with running time O(n log^2 n loglog n) for any constant eps.
1- A (1+eps)-approximation algorithm with running time O(n log^2 n loglog n) for any constant eps.
− 2- The first (1+eps)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i.e., when the stream consists of insert and delete operations of points from a discrete space [1,\dots,Delta]^2. The streaming algorithm uses poly(log Delta/eps) space.
2- The first (1+eps)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i.e., when the stream consists of insert and delete operations of points from a discrete space [1,\dots,Delta]^2. The streaming algorithm uses poly(log Delta/eps) space.
The decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm. This in fact simulates a variation of partitioning oracle approach in the streaming model.
The decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm. This in fact simulates a variation of partitioning oracle approach in the streaming model.