Bureaucrats, editor, Administrators
373
edits
Changes
→Speaker
== Title ==
== Title ==
Property Testing in Planar Graphs and Euclidean Facility Location in the Streaming Model
== Speaker ==
== Speaker ==
Morteza Monemizadeh
== Abstract ==
== Abstract ==
We show that there is a novel and simple decomposition of an input point set P into small subsets P_i, such that:
We show that there is a novel and simple decomposition of an input point set P into small subsets P_i, such that:
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.
Using this decomposition we obtain two main results:
Using this decomposition we obtain two main results:
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.