CSE 521 Assignment #4
Winter 2010

Due: Thursday, March 4, 2010 in class.

Reading Assignment: Kleinberg and Tardos Chapter 8 and the Linear Programming Notes, especially 7.6 and following.

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.)

Whether or not the problem asks for it explicitly, you are required to prove that your algorithms do what you claim and give a runtime analysis.

A final piece of advice: Begin work on the problem set early and don't wait till the deadline is only a few days away.

Problems:

  1. Kleinberg and Tardos, Chapter 8, Problem 17, page 513.

  2. Kleinberg and Tardos, Chapter 8, Problem 32, page 521.

  3. Kleinberg and Tardos, Chapter 8, Problem 34, pages 522-524.

  4. Consider the following linear program P:
    Maximize x1+2x2+x3
    Subject to:
    3x1+2x2+4x3≤6
    x1+x2+x3≤2
    3x2-2x3≤ 0
    x1,x2,x3≥ 0

    1. Use the simplex algorithm to find the solution that achieves the optimal value of P. Show each step.

    2. Write the dual P' of P.

    3. Use the simplex algorithm to solve for the dual optimum solution of P'. Show each step.