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.