Combinatorial algorithms for data migration to minimize average completion time (Q1024212)

The data migration problem is to compute an efficient plan for moving data stored in a network. It is modeled by a graph whose vertices represent storage devices and whose edges represent data transfers. Each vertex has a non-negative weight and each edge has a processing time. A vertex completes, if all edges incident with this vertex are processed. Two edges incident with a vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. \textit{Y. Kim} [J. Algorithms 55, 42--57 (2005; doi:10.1016/j.jalgor.2004.07.009); cf. Zbl 1095.68549] designed a 3-approximation algorithm in the case of unit processing times by using LP-rounding. The authors present a simple, purely combinatorial algorithm which has the same performance guarantee. The same idea leads to a 5.83-approximation algorithm when the edges have arbitrary processing times. Secondly, the authors deal with the problem to minimize the sum of completion times of edges which is equivalent to find a partition of the edge set into matchings \(M_1, M_2,\dots\) so as to minimize \(\sum_i i|M_i|\). This is a variant of open shop scheduling. A simple algorithm which achieves an approximation ratio of \(\sqrt{2}\) is given, which improves the 1.796 ratio presented by \textit{R. Gandhi} et al. [ACM Trans. Algorithms 2(1), 116--129 (2004)]. An example on which the algorithm yields a 1.375-approximate solution shows that the analysis is rather tight.