Cse.iitd.ernet.in

• Write your answers briefly and in clear logical sequence. Meaningless rambling will receive • Answers must be submitted by email in pdf/word format.
• You must not consult any book, internet or any source other than your notes while answering 1. Consider the following LP relaxation for the weighted vertex cover problem. You are given a graph G = (V, E) with vertex weights wv for each v ∈ V . The LP has variablesxv for each vertex v ∈ V . The LP is as follows : What can you say about a basic solution for this LP relaxation ? Use properties of abasic solution to get a 2-approximation algorithm for this problem.
2. A graph is said to be 4-colorable if given 4 colors, we can color each vertex with one of these 4 colors such that the end-points of any edge receive different colors. Give a 3 -approximation algorithm for the weighted vertex cover problem for such graphs.
3. The maximum coverage problem is defined as follows : we are given a set U and a set of subsets S = S1, . . . , Sm of U . The goal is to pick at most k of the subsets in Ssuch that the cardinality of their union is maximized. We know that a simple greedyalgorithm gives a constant factor approximation for this problem. However, we wouldlike to come up with an approximation algorithm based on randomized rounding. So,consider the following natural LP relaxation for this problem : Suppose we are given an optimal solution x∗, y∗ to this LP relaxation.
(a) Suppose we try the following algorithm : consider the sets in the order S1, S2, . . . Sm.
When considering the set Sj, we toss a coin with probability of Heads equal to y∗jand pick this set if the outcome is Heads. Show that there are instances for whichthis algorithm can yield infeasible solutions with high probability (i.e., you shouldshow an instance, an optimal fractional solution and argue why the randomizedrounding will fail with high probability).
(b) Give a different scheme based on randomized rounding which always picks at most k sets and has constant expected approximation ratio.
4. Recall that we say that a graph G = (V, E) has expansion α if |δ(S)| ≥ α|S| for any set S ⊂ V , |S| ≤ |V |/2. Here δ(S) denotes those edges which have exactly one end-pointin S. The hypercube graph Hn is defined as follows : there are 2n vertices, one vertexcorresponding to each binary string of length n. We join two vertices by an edge if thecorresponding bit strings differ in only one location (for example, if n = 4, we have anedge between the vertices (0, 0, 1, 0) and (0, 0, 1, 1) since they differ in the fourth bitposition only, but no edge between (0, 0, 1, 0) and (1, 0, 1, 1), since they differ in twobit positions). Prove that the expansion of the hypercube graph is at least a constant(independent of n).
5. You are given a graph G = (V, E), |V | = n. An edge e = (u, v) denotes the fact that we would like to send one unit of flow from u to v (such graphs are also calleddemand graphs). In many practical settings, one would like to establish the routing ina virtual tree. The goal is to find a binary tree T with exactly n leaves. Each leaf ofT corresponds to a vertex v ∈ V . For every edge (u, v) ∈ E, we send one unit of flowbetween the corresponding leaves in T along the unique path in T joining them. Now,for an edge f in the tree T , the congestion of f is defined as the total flow on this edge.
• Give an approximation algorithm to find such a tree T which minimizes the sum • Give an approximation algorithm to find such a tree T which minimizes the max- The approximation ratio for both of these algorithms should be of the form O(logc n)where c is a constant (such approximation ratios are also called polylogarithmic ap-proximation ratios).

Source: http://www.cse.iitd.ernet.in/~amitk/semI-2010/csl854/exam-approx.pdf