2-Approximating the Minimum Knapsack Problem
Intro Definition. Given $n$ items labeled by $[n]$, and item $i$ has value $v_{i}$ and cost $c_{i}$, we define minimum knapsack problem as following optimization problem - integer programming in fact. $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i} \\ \text{s.t.}\quad& \sum_{i} v_{i}x_{i} \ge D \\ & x_{i} \in \set{0, 1} \end{aligned} $$ where $D$ is given desire on value. We can devise a naive LP relaxation for this: $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i}\\ \text{s....