LP based heuristics for the multiple knapsack problem with assignment restrictions

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.

The final publication is available at link.springer.com.