## Abstract

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 s_{i}. Each disk d_{j} is characterized by two parameters, namely, its storage capacityC_{j} which indicates the maximum total size of data items that may be assigned to it, and a load capacityL_{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. We study this data placement problem for homogeneous storage systems where all the disks are identical. We assume that all disks have a storage capacity of k and a load capacity of L. Previous work on this problem has assumed that all data items have unit size, in other words s_{i} = 1 for all i. Even for this case, the problem is NP-hard. For the case where s_{i} ∈ {1, ..., Δ} for some constant Δ, we develop a polynomial time approximation scheme (PTAS). This result is obtained by developing two algorithms, one that works for constant k and one that works for arbitrary k. The algorithm for arbitrary k guarantees that a solution where at least (frac((k - Δ), (k + Δ))) (1 - frac(1, (1 + sqrt(frac(k, (2 Δ))))^{2}))-fraction of all clients are assigned to a disk (under certain assumptions). In addition we develop an algorithm for which we can prove tight bounds when s_{i} ∈ {1, 2}. In fact, we can show that a (1 - frac(1, (1 + sqrt(⌊ k / 2 ⌋))^{2}))-fraction of all clients can be assigned (under certain natural assumptions), regardless of the input distribution.

Original language | English (US) |
---|---|

Pages (from-to) | 144-167 |

Number of pages | 24 |

Journal | Journal of Algorithms |

Volume | 60 |

Issue number | 2 |

DOIs | |

State | Published - Aug 1 2006 |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics