Approximations

Question 1

Approximation ratio

Answer 1

C is the approximated solution and C* is the optimal one.
For a maximum problem:
C/C ≤ p
For minimum problem:
C/C ≤ p

Question 2

Vertex cover approximation algorithm

Answer 2

Choose a random edge, take both of its nodes for the cover set. Remove that edge and all of the edge going out from both of the nodes from the choosing set.
Approximation of 2.

Question 3

Bin Packing approximation

Answer 3

For each item enter it to the first box that has room for it, if there is no such box, add a new box.
The algorithm leaves in the worst case each box half empty, which is a 2 ratio approximation.

Question 4

Make span scheduling approximation

Answer 4

Sort all the missions by length. Then one by ne enter each mission to the machine that has the shortest working time. This gives an approximation of 2, since the start time of the mission i that causes the machine to be the longest is less than the average before inserting i. Also the avarege of all missions is less than the optimal and so is the run time of i.

Question 5

Integer knapsack approximation

Answer 5

1. Pick the item with the highest value that fits and stop.
2. Take the items by their absolute value per volume until no more can fit.
3. Take the max of both 1 and 2.

This has an approximation of 2, since

ALG1=vmax
OPT*=ALG2+rvk (r<1)
ALG3=max(ALG1,ALG2)

OPT*≤ ALG2+vk≤ ALG2+ ALG1 ≤ 2ALG3

Question 6

Set Cover approximation

Answer 6

Each time selct a group that has the most members that are not yet covered. This yields an approximation of H(|S’|) where S’ is the largest group in S.
H(n) = 1 + 1/2 + 1/3 +… + 1/n

Question 7

The Metric K center Problem (McDonalds problem)

Answer 7

There is no approximation algorithm that is better than a ration of 2.
Proof using reduction from dominating set, given G, where if an edge was in G its weight is 1 and if not it is 2. If to the k center problem, the largest distance is 1, we now that there is a dominating set that is less that or equal k. If the largest distance is 2, there is no dominating set less that or equal to k. Finally if we assume that there is an algorithm to approximate this in less than a 2 ratio, than we get that we can determine the dominating set problem in polynomial time which means that p=np.

Question 8

Metric TSP2 ratio

Question 9

Max-Sat approximation (maximum number of clauses that can be true)

Answer 9

Choose random values for all variables, if you have less that half of the clauses set to true than choose the opposite for all variables, resulting in at least half of the clauses set true. Approximation ratio of 2.