The subset assignment problem for data placement in caches

摘要

This paper gives an approximation algorithm for the subset assignment problem (SAP). Given a set of n items of varying sizes, a set of d bins of varying capacities, and a cost c(p,S) associated for each item p and subset S of bins, the objective of SAP is to place the items in the bins at minimal cost. An item may be assigned to more than one bin. Also, there is a cost to not assigning an item to any bin.