Greedy algorithms for the minimization knapsack problem: average behavior (Q733910)

The authors study the average behaviour of primal and dual greedy methods for the solution of the following knapsack problem: \[ \min \left\{ \sum^{n}_{j=1} c_{j}y_{j} \mid \sum^{n}_{j=1} a_{j}y_{j} \geq d, y_{j} \in \{0,1\}, j=1,\dots,n\right\}. \tag{P} \] The coefficients \(c_{j}, a_{j}\) are assumed to be independent random variables uniformly distributed over \([0,1]\). If \(\mathcal{A}_{n}\) denotes the primal or dual greedy algorithm for the solution of (P), \(g^{\mathcal{A}_{n}}\) the resulting objective function value, and \(g^{*}\) the optimal value of (P), \(\mathcal{A}_{n}\) is said \textit{to have asymptotical tolerance \(t > 0\)}, if \({\mathbf P}(g^{\mathcal{A}_{n}}-g^{*} \leq t) \rightarrow 1 \text{ for } n \rightarrow \infty\). The main result of this paper is the following: If \(d=\mu n\) with \(\mu < t/3\), then the primal and dual greedy methods for (P) have asymptotical tolerance \(t\).