Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

The

data migration

problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges represent the data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has unit processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (

Journal of Algorithms, 55:42-57, 2005

) gave an LP-rounding 3-approximation algorithm. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee, which can be extended to yield a 5.83-approximation for arbitrary processing times. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the completion times of edges. We present a simple algorithm that achieves an approximation ratio of

${\sqrt{2}}$

≈ 1.414, thus improving the 1.796-approximation given by Gandhi

et al.

(

ACM Transaction on Algorithms, 2(1):116-129

, 2006). We show that the analysis of our algorithm is almost tight.