Approximation Algorithms for Data Migration with Cloning
Justin Wan
Department of Computer Science
University of Maryland

Feb 6, 2004
11-11:50 AM
Room 3464 (Math-CS Conference Room), HKUST


Abstract
--------
Our work is motivated by the problem of managing data on
storage devices, typically a set of disks. Such high demand
storage servers are used as web servers, or multimedia
servers for handling high demand for data. As the system is
running, it needs to dynamically respond to changes in
demand for different data items. In this work we study the
data migration problem, which arises when we need to
quickly change one storage configuration into another. We
show that this problem is NP-hard. In addition, we develop
the first polynomial-time approximation algorithms for this
problem and prove a worst case bound of 9.5 on the
approximation factor achieved by our algorithm.

A special case of the data migration problem is to allow
only one source copy for each data item, for which we
develop a polynomial-time 3+o(1) approximation algorithm. We
also considered other restricted cases of the data migration
problem, and develop algorithms with better approximation
factors. All the mentioned problems are generalizations of
gossiping and broadcasting problem, which were heavily
studied.

This is joint work with Samir Khuller and Yoo Ah Kim.