We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d(1), d(2),..., d(N). We are also given sets U-1, U-2,..., U-M such that U-i is the set of clients seeking the ith data item. Data item i has size si. Each disk d(j) is characterized by two parameters, namely, its storage capacity C-j which indicates the maximum total size of data items that may be assigned to it, and a load capacity L-j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data items to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.
展开▼
