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

Homework # 3
Due November 5

1. Give a linear program for the optimal pipeline problem described in lecture 4.
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.
   • 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. Consider the following LP.
   
   subject to , , , .
   • Draw the feasible set.
   • Determine graphically the solution.
   • Which vertices of the feasible set would the simplex algorithm visit en route to the solution?
5. What is the dual problem of the following linear program?
   
   subject to , , .

 
• About this document ...