MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel

Handout 2

HW 1. Given 10/9/2003, Due 10/17/2003, in class.

No collaboration allowed.

1. The textbook mentions (proposition 2.13) that if all edge-costs are integers, Ford’s algorithm terminates after at most Cn² steps, where C = O(max{|c_e|}). Does that make Ford’s algorithm a polynomial time algorithm? Is Bellman-Ford a polynomial time algorithm? Why or why not?

2. In the dynamic programming algorithm for all pairs shortest paths described in class, how would you modify the algorithm to allow easy recovery of the shortest path between any two nodes?

3. Prove that there always exists a sequence of n-1 relaxations which results in the termination of Ford’s algorithm, assuming that there are no negative-cost directed cycles.

4. Consider problem 2.35 from the text. Ignore the solution suggested in the text. Instead, show how this problem can be reduced to a shortest path problem.

5. You are given a set of n positive integers, x₁, x₂, …, x_n. Write a dynamic program to find out if they can be partitioned into two disjoint subsets such that the sum of the numbers in each subset is the same.

6. Suppose there are n cities along a river, at positions x₁, x₂, … , x_n. We have to choose p of these cities as docks such that the sum, over all cities, of the distance of the city to the nearest dock is minimized. Present a dynamic programming algorithm for this problem.

7. Imagine you want to ship some goods from node s to node t in a network. Any edge uv has a failure probability p(u,v). Different edge failures are independent, so the probability that an attempt to send the goods along a path P = v₀v₁v₂…v_k will be successful is
(1-p(v₀v))(1-p(v₁v₂))…(1-p(v_k-1v_k)).
The goal is to find a most reliable path. Reduce this to a shortest path problem that can be solved using Dijkstra’s algorithm.

MS&E 217: Do problems 1,2,3,4 and any one of problems 5,6, and 7.

MS&E 317: Do problems 3,4,5,6,7.

Note: MS&E 217 students may choose to solve more than one out 5,6,7 for practice/feedback. In that case, I will read all your answers and give comments, but please indicate which of the three you want me to actually grade.