Access Restriction

Author Rajiv, G. ♦ Shachnai, Hadas
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Data Migration ♦ Open Shop ♦ Unfounded Assumption ♦ Side Effect ♦ Minimum Sum Version ♦ Non-deterministic Open Shop ♦ Maxim Sviridenko ♦ Approximation Ratio
Abstract In [1], 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 by modifying the analysis. A side effect of this is that the approximation ratio is improved to 4.96. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2011-01-01