A note on the solution of group knapsack problems

From MaRDI portal





The paper is concerned with the following problem: \[ \hbox{Minimize}\quad\sum^ n_{i=1} c_ ix_ i\quad (c_ i>0, x_ i\geq 0)\quad\hbox{s.t.}\quad \sum^ n_{i=1} g_{ij}x_ i\equiv g_{0j}(\varepsilon_ j)\quad\hbox{for}\quad 1\leq j\leq r, \] where \(g_{ij}\), \(g_{0j}\), \(\varepsilon_ j\) are integers with \((g_{01},\dots,g_{0r})\neq(0,\dots,0)\). The paper gives an approximation algorithm, which is an improvement of Shapiro's. The fundamental idea is that the problem can be reformalized as a shortest path problem. Some numerical tests are also included.











This page was built for publication: A note on the solution of group knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979526)