6.856 Randomized Algorithms, Homework 5 (Solutions)

6.856 — Randomized Algorithms Handout #12 — Homework 5 Solutions M. R. refers to this text: Motwani, Rajeez, and Prabhakar Raghavan. Randomized Algorithms. Cambridge: Cambridge University Press, 1995. Problem 1 Randomized selection. We will use the two-point sampling scheme described in class, which only requires O(log n) random bits, to choose the random elements needed for the selection algorithm. This sam­ pling scheme assumed that the number of elements n was actually a prime. There are several way to circumvent this assumption for our problem. Perhaps the easiest is to increase n to a prime. To do this, identify a prime p, n < p < 2n (this can done in linear time). Add p − n new elements of value ∞ to the array, so that the k-th element of the original array is still the k-th element in the new array. Note that since we have at most doubled the number of elements, running in linear time on the new set implies we run in linear time on the original set. So we can now assume without loss of generality that n is in fact a prime. We now apply the algorithm in the book. Since the book analysis only uses the Chebyshev bound, it works so long as the variables being analyzed are pairwise independent. Since the selections via two-point sampling are pairwise independent, we know that the variables Xi in the textbook analysis are pairwise independent. It follows that the algorithm failure probability is O(n−1/4 ). To decrease this failure probability, run that algorithm 4 times, using an independent O(log n)-bit seed for the pairwise independent choices in each run. This still requires O(log n) random bits. This approach fails only if all 4 runs fail to find the k-th element, which happens with probability O(1/n). Note this relies on the fact that in a single run of the original algorithm, we know whether or not we find the k-th element. Problem 2 MR 5.12. We observed in class that the size of the partition is equal to n plus the number of “split” events that occur when an edge crosses some autopartition line (cf. section 1.3 in the text). We build a permutation such that the algorithm that chooses split edges in this permutation order produces a tree of size O(n log n). We do so by walking down a decision tree where the i-th decision level corresponds to choosing which line appears at position i in the permutation. Suppose that we have already selected a prefix πk of edges, say πk = e1 , . . . , ek , to head the permutation and now want to select edge ek+1 from those remaining. Let S denote the number of split events that occur in our autopartition; we know 1 that when we select our permutation uniformly at random, E[S] = O(n log n). We also know by conditional expectations that 1 � E[S | πk ] = E[S | πk , ek+1 ]. n−k e k+1 It follows that there always exists some ek+1 such that E[S | πk , ek+1 ] ≤ E[S | πk ]. If we always select such an extension, then after n steps we have a permutation πn for which the value E[S | πn ], which is just the (deterministic) number of split events in πn , is O(n log n). In order to find the right permutation, we need only be able to compute E[S | πk ] for any πk . Let v1 , . . . , vr = v be the set of edges that are on the line extending from u to v. If any of the vi appear in the permutation before u, then they “protect” v from being split by u. Unfortunately, the converse is not true, since there might be edges not among the vi whose extension protects v from u. But assume that from now on we assume that extensions of edges do not protect other edges from being cut. This might make the BSP tree larger, because more splits occur. But the analysis given above and in class still applies, making the expected size O(n log n). So we can apply the method of conditional expectations to arrive at a BSP of size at most O(n log n). If any of vi appears in the permutation before u, then they “protect” v from being split by u. If none does, then v is split by u — we write u � v. It follows that � E[S | πk ] = Pr[u � v | πk ]. u,v Therefore we only need to be able to compute Pr[u � v | πk ] in polynomial time. Now clearly, Pr[u � v | πk ] = 0 if some vi is in πk and u is not, or if some vi precedes u in πk , while Pr[u � v | πk ] = 1 if both u appears in πk before all vi , and finally Pr[u � v | πk ] = 1/(r + 1) (∗) if none of u or v1 , . . . , vr is in πk (since the probability is 1/(r + 1) that u will be picked before all the vi ). Since we can compute these probabilities (it is trivial to find the intersection points of lines, and then sort the results), we can implement the conditional expectations algorithm. 2 Problem 3 MR 5.11. (a) At a certain node of the conditional probability tree, consider a particular set for which k items remain to be placed. Depending on the items which have already been assigned values, there is a certain maximum√number n+ of items that can receive value +1 without breaking the balance limit of O( n log n) (by having too many positive items), and a certain minimum number n− of items that can receive value +1 without breaking the limit (by having too few positive items). The probability that we get exactly j of our k values assigned +1 is just � � k −k 2 , j �� since each of the 2k assignments is equally likely, and kj of them give k values +1. We simply need to sum this over n− ≤ k ≤ n+ . Thus, the probability that a particular row deviates from balance is a sum of binomial coefficients times a power of two, where the power of two is at most n − i since k ≤ n − i. But P̂ (a) is just a sum of these sums. �� (b) We work with binomial coefficients kj where k ≤ n. So we start by pre-computing �� the O(n2 ) values kj in O(n2 ) time using Pascal’s triangle (note that this uses only additions, no multiplications). Then computing P̂ (a) is just some table lookups, shifts (for powers of two) and adds. In the unit-cost RAM, we� �are done. In the log-cost RAM, we must observe that the operands have size O(log nk ) = O(n) bits so that the individual addition operations take O(n) time. � (c) Let Pi (a) be the probability that row i deviates given a. We have P̂ (a) = Pi (a). Since Pi is a probability, we know that 1 1 Pi (a) = Pi (b) + Pi (c). 2 2 It follows that P̂ (a) = � Pi (a) �1 = �1 = 1 1 P̂ (b) + P̂ (c) 2 2 2 Pi (b) + 2 Pi (c) The result follows. (d) In unit cost RAM we use O(n2 ) time to pre-compute the binomial coefficients. Comput­ ing Pi (a) then requires adding O(n) binomial coefficients for work O(n), which means O(n2 ) work suffices for P̂ (a). We need to do this over O(n) levels of tree for O(n3 ) total work. If we use a log-cost RAM, each addition takes O(n) time (since all coefficients are ≤ 2n ), so the total time rises to O(n4 ). 3 Problem 4 MR 4.13. Let M be the set-incidence matrix where Mij = 1 if j is in set i. We start with an integer linear program based on the set-incidence matrix M . Let mi be the i-th row of M . Let xi be the decision variable that is 1 if the i-th element is included in the set cover, and 0 otherwise. The ILP is � min xi mi x ≥ 1 (∀i) x ∈ {0, 1} � Now we solve the LP relaxation; this gives fractional xi such that mi x ≥ 1 but xi is at most the optimum set cover. Now let us multiply each xi by 3 ln n. If this creates any xj ≥ 1, we include j in our set. For all xj < 1, we include xj in our set with probability xj . Now consider some mi . There are two possibilities. If the scaled up xj ≥ 1 for some mij = 1, then we take xj and thus cover set Si . In the case that all the xj for which mij = 1 are less than 1, then we have a set of Poisson trials to decide which of them get included in our set. But note that the expected number of elements we include is � xj ≥ 3 ln n j∈Si since originally the sum exceeded one and we multiplied by 3 ln n. Now a Chernoff bound argument shows that we include at least one element with probability at least 1 − 1/n3/2 . So with high probability we include an element from every set. It remains to analyze the value of the solution. Its expected value is at most 3 ln n times the optimum, so by applying a Chernoff bound, we see that we get within 6 ln n of the optimum with probability > 1 − 1/n. We can combine the high probability results to say that with high probability we get a solution that is both feasible and cheap (this requires saying; a priori one might fear that if we condition on being feasible, the cost goes up too high). If we don’t we can keep trying until we do (note that we can compare our cost to the cost of the optimal LP solution to get a bound on the quality of our solution); this gives a Las Vegas algorithm. 4