Abstract:
The authors show that for any separable assignment problem (SAP), if there exists an B-approximation algorithm for solving the single bin case, then there is an LP-based algorithm that yields an (1-1/e - ε)-approximation and a local search algorithm with a (1/2-ε)-approximation. A SAP is defined as follows: Given a set of bins and items to pack into bins, a value f_ij for assigning item j to bin i, and a separate packing constraint on each bin (defined by a set of subsets of items that fit into bin i), find the packing that maximizes the aggregate value.