A 4-Approximation Algorithm for the Multiple Knapsack Problem with Color Constraints

In this paper, we present a 4-approximation algorithm for the multiple knapsack problem with color constraints (MKCP). Motivated by a real application from the steel industry, MKCP generalizes the multiple knapsack problem by adding a new attribute (called "color" in this paper) to an item and then adding the associated "color" constraints which restrict the number of distinct colors which can be assigned to a knapsack. The color constraints provide a representation for a general class of processing constraints.