**Due: Thursday Oct 3, 2013, in class**

Undergraduate students can work in teams of two students and can submit a single paper per team. Problems marked (grad) are optional for undergraduate students.

Any notation that is not explained is standard notation. Search google for the definition.

**Problem 1: ** Consider the vertex cover problem discussed in class for Graph $K_3$. Write the linear programming (LP) relaxation for the problem and give the optimal fractional solution. Write the dual LP and prove that your answer is indeed optimal (find a feasible dual solution whose cost equals that of the primal).

** Problem 2: (grad)** Relax the LP from Problem 1 by removing the condition that variables $x_v$ associated with the vertices of $K_3$ must be non-negative. Explain how you obtain the dual of the LP in this case. Write this dual LP.

**Problem 3:** Solve Problem 1.4 b from the textbook. Briefly argue that your algorithm runs in time polynomial with the problem size.

**Problem 4: (grad) ** Solve Problem 1.4 a in the textbook. Hint: read the textbook.

**Problem 5:** Describe the local search approximation algorithm for scheduling jobs on identical parallel machines completely, ** including any data structures ** that you are using. Try to describe an algorithm that is as fast as you can. Analyse the running time of your algorithm.