Bureaucrats, editor, Administrators
373
edits
Changes
→Speaker
Line 1:
Line 1:
Profit Maximization of Seller over Social Markets+Hamid Mahini, Postdoctoral Research, University of Maryland+
== Title ==
== Title ==
−Property Testing in Planar Graphs and Euclidean Facility Location in the Streaming Model
== Speaker ==
== Speaker ==
−Morteza Monemizadeh
== Abstract ==
== 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 22:
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.