What is the probability of the success

Assignment Help Data Structure & Algorithms

Reference no: EM132708521

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, c_o) 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 c 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 c₀ ∈ 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 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.1vi)(vi + 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.

Reference no: EM132708521

Questions Cloud

How cross-cultural differences influence the performance : How cross-cultural differences influence the performance in an international company with specific examples; this part should be written in a problem-solution

Compare vertical and horizontal scaling : List five to ten potential relationships that align with the Pareto principle, such as how 80 percent of sales come from 20 percent of customers.

What is the forecasted external financing needed : What is the forecasted external financing needed if all revenues, expenses, and assets remain a constant percent of sales, and sales increase by 30%?

What is the economic order quantity : ABC has a demand (which is deterministic) for 27,000 DVD's per month. The cost of a DVD is $2.30 and the holding cost is 30 percent of the cost of the product

What is the probability of the success : What is the probability of the success and Will this work to preserve approximately all pairwise distances with high probability? Why

Number of failures with oxygen masks : The fire department has a number of failures with its oxygen masks and is evaluating the possibility of outsourcing the preventive maintenance to the manufactur

How enterprises firms improve their security environment : The assignment is to promote awareness of various security threats, and to develop a better understanding of how enterprises/business firms improve.

Calculate the unit product cost and total gross margin : Calculate the unit product cost and total gross margin for each of the three product lines using the following methods: (a) physical measure method

Describe missing values and pick a technique : Describe missing values and pick a technique that we have not discussed in this class to handle them 3. Discuss why and when do we need to use data.

User Account

All Pages