LP based heuristics for the multiple knapsack problem with assignment restrictions |
| |
| Authors: | Geir Dahl Njål Foldnes |
| |
| Affiliation: | (1) Centre of Mathematics for Applications and Department of Informatics, University of Oslo, P.O. Box 1053 Blindern, 0316 Oslo, Norway |
| |
| Abstract: | Starting with a problem in wireless telecommunication, we are led to study the multiple knapsack problem with assignment restrictions. This problem is NP-hard. We consider special cases and their computational complexity. We present both randomized and deterministic LP based algorithms, and show both theoretically and computationally their usefulness for large-scale problems. |
| |
| Keywords: | Multiple knapsack problem Randomized rounding Traffic routing |
| 本文献已被 SpringerLink 等数据库收录！ |
