Advanced Algorithms Homework 2 Solution

Note: Homework should be submitted in pairs on Canvas. We will only accept PDF files.




(Max Cut.) In the Max-Cut problem, we are given an unweighted graph G with vertex set V and edge set F ; Our goal is to partition V into V1 and V2, so that the total number of edges “cut” by the partition, jF \ (V1 V2)j, is maximized. Consider the following randomized algorithm: for every vertex v 2 V , independently flip an unbiased coin; Let V1 be the set of all vertices for which the coin came up heads, and let V2 be the remaining vertices.



What is the expected number of edges cut?



Determine an upper bound on the probability that fewer than jF j=4 edges were cut. Try to obtain as small a bound as you can.



(Chernoff Bound.) Extend the Chernoff bound discussed in class to the case of arbitrary random variables Xi 2 [0; 1] following the approach below.



(a)
Recall that a function f mapping reals to reals is said to be convex if and only if for every a; b
2 <
,


f(a)+f(b)
f(
a+
b
). Show that f(x) = etx for any t 2 < is a convex function.




2
2






Jensen’s inequality says that for any convex function f and any real-valued random variable X, E[f(X)] f(E[X]). Use Jensen’s inequality to show that if C is a random variable taking values in [0; 1], and B is a f0; 1g random variable with E[C] = E[B], then for any convex f, E[f(C)] E[f(B)].
Use the above parts to reprove the Chernoff bound for sums of independent random variables over [0; 1].



(Longest Path.) In the k-Path problem, we are given an unweighted graph G = (V; E) with special nodes s and t and a target integer k; Our goal is to determine whether there exists a simple path from s to t in G with at least k intermediate nodes. This problem is NP-hard. (Think about why.) In this question you will develop an FPT algorithm for it using a technique called “color coding”.



Consider the following variant of the k-path problem that we will call Colorful k-Path. In this variant, every vertex in the graph G is colored using one of k distinct colors. A path from s to t is called “colorful” if all of the intermediate nodes on this path have different colors. Note that colorful paths are always simple. In the colorful k-path problem, our goal is to determine whether there exists a colorful path from s to t in G with at least k intermediate nodes. Prove that this problem is FPT with parameter k.



Use your algorithm from part (a) to develop a randomized algorithm for the k-path problem that returns a path of length k, if one exists, with probability at least 1 1=poly(n). Your algorithm should run in time O(2O(k)poly(n)) where n is the number of nodes in G.
Hint: consider coloring nodes randomly and applying your algorithm from part (a).




(Dual Fitting for Set Cover.) Recall that in the Set Cover problem, we are given a ground set of elements E = fe1; e2; ; eng and a collection of subsets S = fS1; ; Smg with Sj E and costs cj for all j 2 [m]. Our goal is to find the cheapest collection of subsets that covers the entire ground set E.



In this problem, you will analyze the following greedy algorithm for set cover using a technique called “dual fitting”.




(i) Start with T ; and F E.




While F 6= ; do:



Let j 2 [m] be the index for which cj=jSj \ F j is minimized. That is, set Sj has the smallest cost per element added.






Add j to T and remove the elements in Sj from F .




Return T .



Now answer the following questions.




In class we developed an LP relaxation for the set cover problem. Call this program PRIMAL. Write down the dual of the program PRIMAL. Call it DUAL.



For this part, assume that all of the costs cj are equal to 1. This is the unweighted version of the set cover problem. The greedy algorithm above provides an integral feasible solution to the program PRIMAL. Construct a corresponding feasible solution to the program DUAL such that the cost of the primal solution is within a factor of Hn of the cost of the dual solution. Here Hn is the nth Harmonic number:



n
1
Xi




Hn =
i
:
=1







Conclude that the greedy algorithm gives an O(log n) approximation for the unweighted set cover problem. Hint: First try to construct a dual solution with cost exactly equal to the primal cost, but that violates dual constraints by a factor of at most Hn. Then rescale this dual solution so that it satisfies the dual constraints exactly.




(c) Extend your analysis from part (b) to the weighted version of set cover.





















































































































2