AdvancedAlgorithms Homework 4 Solved

1. Consider the linear programming problem Maximize x1 + x2
Subject to
ax1 +x2 b

x1;x2 ≥0

a. Suggest (in words) a possible real-life scenario that fits this LP. b. Find some values of a and b such that this LP has
i. a unique optimum solution
ii. multiple optimal solutions

iii. no feasible solution (LP is infeasible), iv. no optimal solution (LP is unbounded). For each of the four cases:

1. Illustrate each case with a figure,.
2. Write down the dual LP. Clearly, all four have the same dual program when described

   with a and b. Write the dual program for the values selected in each case. What can you say about the dual linear program in each of the four cases (in terms of feasibility and existence/uniqueness of an optimal solution)?

2. ) In HW2 you provided a 2-approximation to the max-cut problem.
Reminder: Given an undirected graph G=(V,E), a cut is a bipartition (S,V-S) of V. The size of a

cut (S,V-S) is the number of edges with one endpoint on each side of the cut. The maximum cut problem is that of finding a cut of maximum size.

2.1 Explain why the following BIP is a formulation of the problem. For every 𝑣 ∈ 𝑉, let 𝑥􏰆 be a binary variable indicating whether 𝑥􏰆 ∈ 𝑆. For every 𝑒 ∈ 𝐸, let 𝑦􏰈 be a binary variable indicating whether 𝑒 is in the cut.

max ∑􏰉􏰆∈􏰊 𝑦􏰈

s.t 𝑦􏰉􏰆 −𝑥􏰉 −𝑥􏰆 ≤0 forall 𝑢𝑣∈𝐸 𝑦􏰉􏰆+𝑥􏰉+𝑥􏰆 ≤2 forall𝑢𝑣∈𝐸 𝑥􏰆 ∈ {0,1}, forall 𝑣 ∈ 𝑉
𝑦􏰉􏰆 ∈ {0,1}, for all 𝑢𝑣 ∈ 𝐸

2.2 In the LP relaxation, the integrality constraints are replaced by the constraints 0 ≤𝑥􏰆 ≤1 forall 𝑣∈𝑉, and0≤ 𝑦􏰈 ≤1 forall𝑒∈𝐸.

Suggest a 2-approximation algorithm based on rounding, or explain why no such algorithm exists. In the first case, prove the approximation ratio and show that it is tight. In the second case, show that every graph has a useless trivial optimal fractional solution.

3. (25 pts.) Let S ={a1,a2,..,an} be a finite set. Let wi be the weight of element ai
Let C be a collection of subsets of S. That is, Cj  S, for j=1..m.
A hitting set of C is a subset X⊆S that contains at least one element from every subset Cj in C (∀𝐷∈𝐶 𝑋∩𝐷≠∅).
The minimum cost hitting set problem is the problem of finding a hitting set X of minimum weight.

1. Describe the min-cost HS problem as a BIP.
2. Describe the following instance in matrix/vector representation:

   S={a1,a2,a3,a4,a5}, C1={a2,a3,a4}, C2={a1,a5}, C3={a1,a3,a4} All elements have the same weight wi=4.

3. Describe the dual problem (of a general instance) and write its meaning.
4. Assume that for all j, |Cj| k. Suggest a k-approximation algorithm based on

   rounding, or explain why no such algorithm exists. In the first case, prove the approximation ratio and show that it is tight. In the second case, show that every instance has a useless optimal fractional solution.

4. (25 pts.) Oren, our devoted HR worker would like to give special recognition awards to the workers. Every worker can select either an umbrella or a hat with the company logo. Every worker declares her preference in advance. Summing up the workers requests, it turns out that Oren needs to buy 45 umbrellas and 28 hats. The Chinese importer sells two types of packages. The first package costs 80 NIS and includes 4 umbrellas and 4 hats; the second package costs 65 NIS and includes 6 umbrellas and 3 hats. Oren must buy complete packages, and cannot use any leftovers. How many packages from each type should he buy in order to minimize his total cost and satisfy all workers’ requests?

Describe the problem as an Integer Programming problem, and solve it using Branch and Bound. You can use any online LP solver in order to solve the relaxed LP problem in every stage (one possible recommended free solver is Wolfra|Alpha , make sure you add ‘commas’ after every constraint).

Describe in a figure the B&B solution tree. For every node specify the variables’ and the objective function value. Describe in words the order according to which the tree is developed.