Corrigendum: Improved results for data migration and open shop scheduling

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


In Gandhi et al. [2006], we gave an algorithm for the data migration and non-deterministic open shop scheduling problems in the minimum sum version, that was claimed to achieve a 5.06-approximation. Unfortunately, it was pointed to us by Maxim Sviridenko that the argument contained an unfounded assumption that has eluded all of its readers until now. We detail in this document how this error can be amended. A side effect is an improved approximation ratio of 4.96.

Original languageEnglish
Article number34
JournalACM Transactions on Algorithms
Issue number4
Publication statusPublished - 2013

Other keywords

  • Approximation algorithms
  • Data migration
  • Linear programming
  • LP rounding
  • Open shop
  • Scheduling


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

Cite this