A new wireless company, OttoMobile, would like to set up cellular service in the city of Ann Arbor. The company would like to maximize the number of cell towers in the city. However, the city has just passed a rule that a company cannot place cell towers in adjacent neighborhoods. Suppose that there are nneighborhoods and that each neighborhood is adjacent to at most 6 other neighborhoods. The company uses the following randomized algorithm to determine where to place cell towers, where H is the set of neighborhoods and M is the set of pairs of adjacent neighborhoods:
A = -On input
1. Let P = Pi pn be a permutation of H chosen uniformly at random.
2. Let C = 0.
3. For i = 1 to n:
4. If none of pis adjacent neighborhoods have been encountered yet (i.e. none are in the set {pi,… add pi to O.
5. Return C.-
A. Suppose that neighborhood hi has exactly 6 adjacent neighborhoods. Compute the probability that the algorithm assigns ht to the set C.
B. Now suppose that h, has 6 adjacent neighborhoods. What is a nontrivial lower bound on the probability that the algorithm assigns /i, to the set C? Justify your answer.
C. Assuming that each hi has 6 adjacent neighborhoods, compute a nontrivial lower bound on the expected size Ex[j(7|].
D. What is the approximation ratio a the algorithm achieves in expectation? Justify your answer.
