CSE 521 Assignment #5
Winter 2010

Due: Friday, March 12, 2010 by 4:30 pm.

Reading Assignment: Linear Programming Notes. Multiplicative Weight Updates slides.

Instructions: You are allowed to collaborate with fellow students taking the class in solving problem sets. However, you must write up your problem sets individually. If you do collaborate in any way, you must acknowledge for each problem the people you worked with on that problem.

The problems have been chosen for their pedagogical value and hence might be similar or identical to those given out in past offerings of this course at UW, or similar courses at other schools. Using any pre-existing solutions from these sources, from the Web or other algorithms textbooks constitues a violation of the academic integrity expected of you and is strictly prohibited.

Most of the problems require only one or two key ideas for their solution. In writing up your solutions make sure that you clearly write out the main ideas of your solution first so that if you make a mistake in the details you can still get good partial credit for the problem. After you sketch out your solution try to clean up your presentation to make sure that you are only making necessary correct claims since additional incorrect claims will hurt your score.

Please typeset solutions for legibility and hand in hard copies. (The goal for this is not to be time-consuming so don't waste time using drawing programs; hand-drawn diagrams are OK.)

Problems:

1. A multicommodity flow network G=(V,E) supports the flow of p different commodities between a set of p source vertices S = {s₁, . . . , s_p} and p sink vertices T = {t₁, . . . , t_p}. For any edge (u, v) the net flow of the i^th commodity from u to v is denoted f_i(u, v). For the i^th commodity, the only source is s_i and the only sink is t_i. There is flow conservation independently for each commodity: the net flow of each commodity out of each vertex is zero unless the vertex is the source or sink for the commodity. The sum of the net flows of all commodities on an edge (u, v) must not exceed the capacity of the edge c(u, v), and in this way the commodity flows interact. The value of the flow of each commodity is the net flow out of the source for that commodity. The total flow value is the sum of the values for all p commodity flows.

   Give a linear programming formulation for maximizing the total flow value in a given multi-commodity flow network.

2. Consider the following problem of scheduling on unrelated parallel machines: There are n jobs and m machines. The input consists of the nm non-negative integer processing times p_ij which is the time it takes to execute job i on machine j. The goal is to find an assignment of every job to a machine to minimize the makespan which is the maximum total processing time of jobs assigned to any one machine.

   1. Express the problem as an integer linear program. Your program show have a variable x_ij to represent that the job i is assigned to machine j and a variable T to represent the makespan.

   2. Change this program to get a linear relaxation for this problem.

   3. What is the dual of this linear programming relaxation?

   4. What are the relationships between OPT_IP, OPT_LP, OPT_dual-LP?

   5. Use the case that there is a single job to get a lower bound on the integrality gap of the linear relaxation in part (b) (the biggest ratio R between the integer optimum and its optimum).

   6. Suppose that you have an optimal solution (x*,T*) to the linear relaxation. Instead of trying to round this solution deterministically as we did for weighted vertex cover, we can interpret each x*_ij value as a probability that job i should be assigned to machine j. Suppose that we use these probabilities to randomly assign each of the jobs to a machine. Let T_j be the expected total time of all jobs assigned to machine j using this method. What is T_j in terms of the x*_ij?

3. In class we saw how the analysis of multiplicative weight updates can be used to show that a greedy algorithm is a ln(n) factor approximation for unweighted Set-Cover. In the Weighted-Set-Cover problem over the universe U={1,...n} the input consists of a colleciton m sets S_j, each with an input weight c_j, and the goal is to find a sub-collection of sets of minimum total weight that covers U.

   Show how to modify the above multiplicative weight updates argument to prove that a similar greedy algorithm is also a ln(n) factor for Weighted-Set-Cover.