TY - GEN

T1 - Improved algorithms for data migration

AU - Khuller, Samir

AU - Kim, Yoo Ah

AU - Malekian, Azarakhsh

PY - 2006/1/1

Y1 - 2006/1/1

N2 - Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in [Khuller, Kim and Wan: Algorithms for Data Migration with Cloning, SIAM J. on Computing, Vol. 33(2):448-461 (2004)]. In this paper we develop an improved approximation algorithm that gives a bound of 6.5 + o(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5. We also consider the full duplex communication model and develop an improved bound of 4 + o(1) for this model, with no external disks.

AB - Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in [Khuller, Kim and Wan: Algorithms for Data Migration with Cloning, SIAM J. on Computing, Vol. 33(2):448-461 (2004)]. In this paper we develop an improved approximation algorithm that gives a bound of 6.5 + o(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5. We also consider the full duplex communication model and develop an improved bound of 4 + o(1) for this model, with no external disks.

UR - http://www.scopus.com/inward/record.url?scp=33750050812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750050812&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33750050812

SN - 3540380442

SN - 9783540380443

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 175

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a

PB - Springer Verlag

T2 - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006

Y2 - 28 August 2006 through 30 August 2006

ER -