Tight Approximation Algorithms for Maximum General Assignment Problems

This paper studies a general class of maximizing assignment problems with packing constraints. In particular, one studies the Separable Assignment Problems (SAP): one is given a set U of n bins and a set H of m items, and a value, fij, for assigning item j to bin i. One is also given a separate packing constraint for each bin i; packing here refers to the assumption that if a subset is feasible for a bin then any subset of it is also feasible. The goal is to find an assignment of items to bins with the maximum aggregate value. For each bin, one defines the single-bin subproblem as the optimization problem over feasible sets associated with the packing constraint for the bin.