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.