`|= `@=

Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 2000

Homework # 4
Due 4pm, October 27

Reading: see slides

Problems

1.

Give a linear program for the optimal pipeline problem discussed in lecture 4 - A D bit data object must be sent through a pipeline of n stages. The time it takes an x bit packet to get through stage i is $o_i+{x \over b_i},$ where o_i is the overhead of the i-th stage and b_i is the bandwidth of the i-th stage (in bits/sec). Your linear program should determine how the data should be broken up into k pieces, not necessarily of equal size, so as to minimize the time through the pipeline.

2.

We discussed the problem of finding a maximum flow in a graph G=(V,E) with capacities c(v,w) on each edge $(v,w)\in E$. Formulate this problem as a linear programming problem.

3.

Drawing graphs nicely is a problem that arises constantly in applications. Consider the problem of drawing a tree. Some characteristics that would be desirable in the drawing are:

• All nodes on the same level in the tree should line up horizontally.
• There should be a minimum horizontal spacing between nodes at the same level.
• The vertical distance between a node and it's children in the tree should not be less than some minimum value m.
• All nodes should lie within a certain window on the screen.
• The parent of a set of nodes should be centered over those nodes in the horizontal direction.
• The height and width of the tree drawing should be small.

How would you formulate the problem of placing the tree nodes in the drawing using linear programming?

4.

(Revised) Let G = (V,E) be a flow network. Show that there is a sequence of at most |E| argmenting paths such that augmenting along these paths in the specified order produces a maximum flow. (Hint: Determine the paths after finding the maximum flow.)