Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses |
| |
| Authors: | A.M. Frieze M.R.B. Clarke |
| |
| Affiliation: | Department of Computer Science & Statistics, Queen Mary College, University of London, London E1 4NS, United Kingdom |
| |
| Abstract: | We describe a polynomial approximation scheme for an m-constraint 0–1 integer programming problem (m fixed) based on the use of the dual simplex algorithm for linear programming.We also analyse the asymptotic properties of a particular random model. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
