**Due: TBD, 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 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.