Algorithm-Design-Homework 2 Solved

Exercise 1
There is an underlying undirected graph G = (V,E) with weights on the vertices, where the weight on vertex v is denoted by wv = d(v) (the degree of the vertex). Your goal is to find a vertex cover set U (a set where for every e = (u,v), one of vertices u,v is in U) with the minimal total weight possible.

Show that any greedy algorithm, gives a 2-approximation to the best vertex cover.

Exercise 2
There are n arbitrary cards on the table each with a different number on it facing down (where n is an even number). You are allowed to flip the cards one by one and decide whether to select it or not before continuing to the next card. You are only allowed to select one card during this process.

1.   Design a randomized strategy that guarantees that you select the card with the maximal value with a probabilityof at least 1/4.

2.   Prove the correctness of the guarantee of the strategy.

Exercise 3
Let G = (V,E) be a directed graph, and let wv be the weight of vertex v for every v ∈ V . We say that a directed edge e = (u,v) is d-covered by a multi-set (a set that can contain elements more than one time) of vertices S if either u is in S at least once, or v is in S at least twice. The weight of a multi-set of vertices S is the sum of the weights of the vertices (where vertices that appear more than once, appear in the sum more than once).

1.   Write an IP that finds the multi-set S that d-cover all edges, and minimizes the weight.

2.   Write an LP that relaxes the IP.

3.   Describe a rounding scheme that guarantees a 2-approximation to the best multi-set.

Exercise 4
Before we begin we will introduce the notion of Price of Stability (PoS). Let NE to be the set of all the equilibrium states, and sOPT to be the state with the optimal Social Cost (SC). Then, the Price of Stability is defined as

 ,

i.e., the ratio between the smallest Social Cost at an equilibrium state, and the optimal Social Cost. Now, consider the following function

#(r,α)

Φ(α) = XX cr(i),

                                                                                                            r∈R       i=1

where α is a strategy profile (α1,...,αn), r ∈ R is a resource, cr is the cost function of resource r and #(r,α) is the number of players using resource r in profile α. This is a potential function and it is called Rosenthal’s potential.

Now consider a congestion game for which we have the following guarantee: The cost functions cr are such that no resource is ever used by more than λ players. Use Rosenthal’s potential to show that the Price of Stability of such a game is at most λ.

Hint: Try to use the observation that by starting from a state that produces the optimal social cost, in case this state is not a

Nash equilibrium, then there is at least one player that by deviating can decrease the potential function.

Exercise 5
[Independent Set] There is an undirected graph G = (V = {v1,...,vn},E). There are a total of n! possible orderings of these vertices. Pick one such ordering uniformly at random σ = (σ1,...,σn). Then consider the following process: Begin with S = ∅. Then, at each step (for i = 1 to n), if for all u ∈ S, (u,vσi) ∈/ E, add vσi to S.

Denote by d the maximum degree of a vertex of V . Prove that the proposed algorithm achieves an independent set with expected value of at least 1/d fraction of the optimal solution.