Improved results for data migration and open shop scheduling

Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceedingChapter

5 Scopus citations

Abstract

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage devices. Kim [13] gave a 9-approximation algorithm for the problem. We improve Kim's result by giving a 5.06-approximation algorithm. We also address the open shop scheduling problem, O|rj|ΣwjC j, and show that it is a special case of the data migration problem. Queyranne and Sviridenko [18] gave a 5.83-approximation algorithm for the nonpreemptive version of the open shop problem. They state as an obvious open question whether there exists an algorithm for open shop scheduling that gives a performance guarantee better than 5.83. Our 5.06 algorithm for data migration proves the existence of such an algorithm. Crucial to our improved result is a property of the linear programming relaxation for the problem. Similar linear programs have been used for various other scheduling problems. Our technique may be useful in obtaining improved results for these problems as well.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJosep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
PublisherSpringer Verlag
Pages658-669
Number of pages12
ISBN (Print)3540228497
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3142

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Improved results for data migration and open shop scheduling'. Together they form a unique fingerprint.

Cite this