Improved approximation algorithms for data migration

Samir Khuller, Yoo Ah Kim, Azarakhsh Malekian*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, 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. Comput. 33(2):448-461, 2004). In this paper we develop an improved approximation algorithm that gives a bound of 6.5 + o(1) using new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5 using external disks. We also consider the full duplex communication model and develop an improved bound of 4 +o(1) for this model, with no external disks.

Original languageEnglish (US)
Pages (from-to)347-362
Number of pages16
JournalAlgorithmica
Volume63
Issue number1-2
DOIs
StatePublished - Jun 1 2012

Keywords

  • Approximation algorithms
  • Data migration
  • Edge coloring

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Improved approximation algorithms for data migration'. Together they form a unique fingerprint.

Cite this