Algorithms – Solutions to Exercise 5

Question 1

(a)

Let’s define . If we can show that it has a single minimum in y=0, and f(y)=0 – it proves that .

à iff iff y=0. But we have to check the second derivative to find if this extremum point is a minimum.

and for y=0 we get à y=0 is a minimum for f(y).

Conclusion: à

(b)

Bernoulli inequality:

Let à for each and , in particular: for .

(c)

Question 2

An example for tight approximation ratio (2-1/k):

Let the input to the algorithm be: k(k-1) assignments of length 1, and a final assignment of length k.

The optimal solution: put k assignments of 1 in the first k-1 slots, and the final assignment with length k in the last, k’th slot. The total length in each slot: k. We’ll call it Q(OPT).

Algorithm’s solution: after k(k-1) steps there will be (k-1) assignments in each of the k slots (total length k-1 in each one) and the last assignment will add k to one of the slots. The result: the longest slot will take (k-1)+k = 2k – 1 units of time. We’ll call it Q(ALG).

The ratio:

Question 3

The algorithm that was shown in class for Subset Sum Problem:

1. L₀ ß{0}
2. for i=1 to n
1. L_i = merge(L_i-1,L_i-1+x)
2. L_i = Trim(L_i,)
3. Remove from L_i elements that are bigger than t
3. return largest element in L_n

We’ll change the algorithm in the following way:

• in 2(b) [Trim] we’ll replace with
• in 2(c) we’ll remove from Li all elements that are bigger or equal to t but we’ll leave the smallest one between them
• in 3 we’ll check if the largest element X holds X ≥ t. If yes à we’ll return it, else we’ll say that there’s no legal solution.

It is clear that these changes provide a legal solution for the problem.

It’s easy to show that the approximation boundary holds here too:

If Z is the optimal solution, and Y is the new algorithm’s solution, then for small enough we get: .

Question 4

A counter example:

Take a simple graph with 1 edge only (u,v) with weights on the vertices: w(u), w(v). It’s obvious that the optimal solution will be to take the vertex with the minimal weight. Without loss of generality, let’s say that the optimal solution is {u} and its weight is w(u). The Vertex-Cover approximation algorithm will choose the edge and take both vertices, so that it’s weight will be w(u) + w(v). Even in this simple case we cannot give any bound to à the approximation algorithm given in class is not working in the weighted case.

Question 5

Let X={1,…,n} be a set of size n and F be a family of subsets of X. Each subset has weight w_S We look for the covering of X by a partial family of subsets such that and is minimal.

The algorithm:

Initialization:

U ß X

C ß

T_i ß S_i , i=1,…k

q ß 0

Iteration:

While U

Pick S in F that minimizes

U ß U-S

CßC{S}

Return C (q(C) will be the returned cover weight).

Now we need to prove that this algorithm provides (ln(M)+1) approximation to the optimal solution q(OPT) when M=max |S_i|.

The proof is an adaptation of the proof in Cormen for the case w_S =1 (no weights) in chapter 36. The cost c_x allocated to each element x is now

As before q(C)=

The key inequality is changed to with the proof following the same lines.