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 k-suppliers problem defined in Exercise 2.1 in the textbook. In class, we argued that choosing an arbitrary vertex as center for the 1-center problem is a 2-approximation algorithm. Show that the same strategy has an unbounded approximation factor for the 1-supplier problem (show that $\forall \alpha > 0$, there exists an instance with $Z_{arb} > \alpha Z_{OPT}$, where $Z_{arb}$ is the cost of an arbitrary center in the 1-supplier problem).

Problem 2 (grad): Consider the following strategy for the 1-supplier problem:

• Choose an arbitrary customer $i \in D$.
• Let $j \in F$ be the closest facility from $i$.
• Place the facility at $j$.

Show that this strategy is a 3-approximation for the 1-supplier problem (ignore the fact that the 1-supplier problem can be solved optimally in polynomial time by a brute force algorithm). Give a 3-approximation greedy algorithm for the $k$-suppliers problem. Prove its approximation factor.

Problem 3: Consider the following greedy algorithm for the knapsack problem, where $i \in I$ represents an object with value $v_i$ and size $s_i$, and $B$ is the knapsack capacity. Let $v(S)$ and $s(S)$ be the total value and size respectively of items in $S$, $v(S) = \sum_{i \in S} v_i$, $s(S) = \sum_{i \in S} s_i$.

• Initialize the solution set $S \leftarrow \emptyset$.
• while the total size of the solution $S$ does not exceed the knapsack capacity, $s(S) \le B$ do:
  • Let $j$ be the object with largest value per unit size, $j = \mathop{\rm argmax}_{i \in I-S} \frac{v_i}{s_i}$.
  • Add $j$ to the solution, $S \leftarrow S \cup \{j\}$
• Return $v(S)$

Give a simple example to show that this greedy algorithm has an arbitrarily small approximation factor.

Problem 4 (grad): Show that replacing the last step of the greedy algorithm from Problem 3 with
\[
\text{Return } \max\{v(S), \max_{i \in I} v_i\},
\]
gives a $\frac{1}{2}$-approximation for the knapsack problem. Provide an example where the greedy algorithm returns a solution with cost equal to half of the optimal solution. Justify your answer even if you cite published work.

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.