Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses (Q789319)

This paper is concerned with the m-dimensional 0-1 knapsack problem: \[ (1.1)\quad Maximise\quad z=\sum^{n}_{j=1}c_ jx_ j, \] \[ subject\quad to\quad \sum^{n}_{j=1}a_{ij}x_ j\leq b_ i,\quad 0\leq x_ j\leq 1,\quad x_ j\quad integer,\quad j=1,...,n;\quad i=1,...,m, \] where for all i, j, \(a_{ij}\geq 0\), \(b_ i\), \(c_ j>0\). m is considered to be a fixed constant. The problem is known to be NP- hard even when \(m=1\) and so there is interest in finding heuristics which work in polynomial time (polynomial in the input length) and have a guaranteed accuracy. Given \(\epsilon>0\) we say that an algorithm is an \(\epsilon\)-approximation algorithm if it always produces a solution \(\hat x\) with objective value \(\hat z\) that satisfies \[ (1.2)\quad z^*-\hat z\leq \epsilon z^* \] where \(z^*\) is the maximum value of z in (1.1). The aim of this paper is two-fold. In Section 2 we present a polynomial approximation scheme for problem (1.1), i.e. for each \(\epsilon>0\) we describe an algorithm \(A_{\epsilon}\), which is an \(\epsilon\)- approximation algorithm and runs in time polynomial in the length of the input description of (1.1). In Section 3 we conduct a probabilistic analysis of this problem and obtain reasonable tight bounds for the asymptotic behaviour of the objective value \(z^*\). A simple consequence of this analysis is that with probability \(\to 1\) as \(n\to \infty\) the solution obtained by rounding down the solution to the linear program (1.1) satisfies (1.2) with \(\epsilon =n^{-a}\) provided \(a<1/(m+1)\).