Reference no: EM132713164

Problem 1

Consider the metric 1-median problem. Let S be a set of N points from a metric space M = (X, d) and let d be the distance function. Let co be the optimal center and let OPT = x S d(x, co) be the optimal cost.

Consider the following simple randomized algorithm. First, we sample a point compute the total cost a S d(c, a). Repeat, this procedure O(1) times and choose uniformly at random. Second, we connect every point from S to and the best solution. Can you derive any approximation guarantee for the resulting solution? What is the probability of the success? You can assume that c0 ∈ S. Solve the same problem assuming c0 ∈ X \ S.

Problem 2

Let X = x1, . . . , xn be a set of n points from d-dimensional Euclidian space. denstrauss transform. For example, let r = O(log(n)/s2) and let A be a random r n matrix where all entries ai,j are i.i.d. random variables with P (ai,j = 1) = To preserve pairwise distances between the points we can use the Johnson Lin- P (ai,j = 1) = 0.5. Let yi = Axi. The JL lemma states that all pairwise distances will be approximately preserved, with high probability.

Consider the following modification. To save time in computing Ax, we may try to "sparsify" the entries of A as follows. Use a random matrix A with i.i.d. random entries ai,j with P (ai,j = 1) = P (ai,j = 1) = 10/r and P (ai,j = 0) = 1 - 20/r . Will this work to preserve approximately all pairwise distances with high probability? Why?

Problem 3
Let v = (v1, v2, . . . vn) be a frequency vector of an insertion-only stream. Define

H(v) := Σ(v2 - 0.1v_i)(v_i + 1).
          i∈[n]

Design an one-pass streaming algorithm to approximate H(v). Give space bound for your algorithm to output a (1 s) approximation with probability at least 0.9. Prove the correctness of your claims.