Difference between revisions of "CATS-Jan-25-2013"
| Line 15: | Line 15: | ||
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: | ||
Revision as of 22:10, 14 December 2012
Title[edit]
Profit Maximization of Seller over Social Markets
Speaker[edit]
Hamid Mahini, Postdoctoral Research, University of Maryland
Abstract[edit]
Recent developments \cite{BSS08,CSS09,HKNO09,NO08} in the area of testing properties for classes of bounded-degree graphs with an excluded minor propose a new technique called "partitioning oracles". A partitioning oracle explores local neighborhoods of sampled vertices and using this, answers queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges.
We take the idea of partitioning oracles as the first step to connect property testing algorithms to streaming algorithms. In this paper, we focus on the the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P \subseteq R^2 and an opening cost f in R^+, and we want to find a set of facilities F \subseteq R^2 that minimizes f |F| + sum_{p in P} min_{q in F} dist(p-q), where dist(p,q) is the Euclidean distance between p and q.
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),
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:
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.
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.
