A class of generalized greedy algorithms for the multi-knapsack problem (Q1803680): Difference between revisions

A class of algorithms is proposed for determining approximate solutions of the following problem: given nonnegative reals \(c_ j\), \(a_{ij}\), \(b_ i\), find \(\max \sum^ n_{j=1} c_ j x_ j\), s.t. \(\sum^ n_{j=1} a_{ij} x_ j\leq b_ i\) for \(i=1,2,\dots,m\), \(x_ j\in\{0,1\}\) for \(j=1,2,\dots,n\). The algorithms choose weights \(w_ 1,w_ 2,\dots,w_ m\) and determine nonzero values of \(x_ j\) in the order defined by the decreasing ratios \(c_ j/\sum^ m_{i=1} w_ i a_{ij}\). The authors investigate the complexity of computing a set of weights which gives the maximum greedy solution value. The heuristics are subjected to both a worst case and a probabilistic performance analysis. It is shown that an upper bound on the worst-case absolute difference between the optimal solution value and maximum greedy solution value is less than \(m\) \(c_{\max}\). Finally, it is proved that the sequence \(\{z^ H_ n(\lambda^*)/z^ I_ n\}\) converges to 1 with probability one, where \(z^ H_ n(\lambda^*)\) is the random variable denoting the solution value determined by the algorithm and \(z^ I_ n\) is the random variable denoting the optimal solution of the problem.