A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, fij
, for assigning item j to bin i; and a separate packing constraint for each bin–i.e., for each bin, a family of subsets of items that fit in to that bin. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (GAP)1 and a distributed caching problem (DCP) described in this paper.Given a β‐approximation algorithm for finding the highest value packing of a single bin, we give
A polynomial‐time LP‐rounding based ((1 − 1/e)β)‐approximation algorithm.
A simple polynomial‐time local search (β/(β + 1) − ϵ)‐approximation algorithm, for any ϵ > 0.
