An efficient approximation for the Generalized Assignment Problem

We present a simple family of algorithms for solving the Generalized Assignment Problem (GAP). Our technique is based on a novel combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for GAP. If the approximation ratio of the knapsack algorithm is α and its running time is O(f(N)), our algorithm guarantees a (1+α)-approximation ratio, and it runs in O(M⋅f(N)+M⋅N), where N is the number of items and M is the number of bins. Not only does our technique comprise a general interesting framework for the GAP problem; it also matches the best combinatorial approximation for this problem, with a much simpler algorithm and a better running time.