Algorithm Design-Homework 2 Solved

Exercise 1
Santa is in a hurry: he has n presents still to deliver to n houses H, and m < n elves E to help him with the task. He wants to take a nice nap now, so he wants his elves to do the deliveries. Unlike himself, the elves unfortunately are not skilled enough to be capable of delivering any present: one cannot climb chimneys, another is too loud and would wake people who have a light sleep, and so on. Santa knows for each e ∈ E which houses He are doable, and since elves are playful creatures, he believes each delivery will take each elf one full hour. As christmas is soon to be over, Santa would like to deliver all presents, but also minimize the time until the last elf is finished.

a)    Help Santa write the problem as an ILP with 0-1-variables. Then relax this to an LP.

b)   Give an algorithm that gets as input an optimal solution to your LP, and outputs a feasible solution to Santa’s problem which is, in expectation, just as good as the LP optimum.

c)    To take away Santa’s worries, show that your algorithm is unlikely to deliver very bad results: prove that with high probability, i.e. at least 1 − 1/m, the resulting solution is no worse than O(lnm + OPT), where OPT denotes the finishing time of the optimal LP solution.

Hint: If X is the sum of independent {0,1}-variables and E[x] = µ 0, then for any :

 

Exercise 2
Santa has a real challenge this year: 187 of his elves were quarantined with Covid 19 during the christmas time, and are now clinically depressed because they missed all of the fun. He wants to give each of them a perfect present, and since they have always envied Santa for his magical sleigh, his idea is to give each of them his own toy sleigh.

Now in the shed, he has a set P of n pieces that will clearly be sufficient to build the sleighs, each of which is available in large amounts. The pieces are such that you will never need more than copy of any p ∈ P for the same sleigh. Santa, as an expert, knows what a good sleigh needs: For example, they might each need a front light, and there might be different ones (p1,...,pl) in P, so you must use p1 or ... or pl. Also, it is important for everything to look great, so he is planning to use at least one red part in each gift and one green one. Actually, Santa has a long list of all kinds of different constraints on the sleigh assembly, which he is writing down similarly as above.

As the new intern, Santa is calling you into his office and while you are eating a nice sugar cane, he tasks you with the following: Tomorrow, it is your job to write and run a polynomial-time algorithm that gets as input a formal depiction of Santa’s constraints, and outputs all 187 different sets of parts for the sleighs (if possible, otherwise return ’no’). Santa promises the assembly will be done by more experienced workers - all you have to take care of is that no two sleighs are exactly the same, so the gifts still feel special enough.

Despite the sugar cane, the assignment leaves a bitter taste in your mouth. However, not wanting to ruin your own christmas, you don’t protest right away: that would look just lazy. Come up with a mathematical proof that in general, this problem is clearly a hard one and might not be solvable for you in a day.

Exercise 3
We have an undirected graph G = (V,E) with |V | players, in which each player i controls exactly one, distinct vertex vi ∈ V . Each edge e ∈ E is associated with a nonnegative weight we. A cut is a partition of the set of vertices into two disjoint sets LEFT and RIGHT. Each player selects the set in which his controlled vertex will be, i.e. the strategy space of each player i is αi = {LEFT,RIGHT} and let α = (α1,...,αn) be the corresponding strategy profile.

Let CUT(α) be the set of edges that have one endpoint in each set and let Ni be the set of neighbours of vi in the graph G. The payoff of player i is defined as

                                                                                      ui(α) =            X           we.

e∈CUT(α)∩N1

1.   Design a cut game in which the Price of Anarchy is 2. Hint:Use a graph with four vertices and unit weights.

2.   Prove that the Price of Anarchy of cut games is at most 2 in the general case, not only for the game with 4 vertices. Hint: First argue that in a pure Nash equilibrium, the total weight of the neighbouring vertices of a vertex vi in the cut is at least half the total weight of all the neighbouring vertices of the vertex.

Exercise 4
Suppose that there is a graph G = (V,E) where the vertices can be of two types: there is a set A of possible antennae locations and a set S of cities, with V = A ∪ S. The graph is complete, i.e. for any pair {x,y} ⊆ V we also have that (x,y) ∈ E. Moreover, the weight of each each edge (x,y) is given by the distance function d : V 2 → R; it satisfies the properties d(x,y) = d(y,x) ≥ 0, d(x,x) = 0 and d(x,z) + d(z,y) ≥ d(x,y), for all x,y,z ∈ V . Our goal, is to select k antennae such that the maximum distance from a city to any chosen antenna is minimized. Specifically, we need to find a U ⊂ A such that |U| = k and

maxmind(x,y) x∈S y∈U

is minimized.

1.   Show that minimizing this objective is NP-hard.

2.   Find a 3-approximation algorithm.

3.   Show that finding an a-approximation with a < 3 is also NP-hard. If you do this, there is no need to include an answer to the first sub-question.