Next: About this document ...
`|=
`@=
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
where oi is the overhead of the i-th stage and bi
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
.
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.)
Next: About this document ...
Ashish Sabharwal
2000-10-26