非表示:
キーワード:
-
要旨:
The \textit{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
edges represent data transfers required between pairs of devices. Each vertex
has a non-negative weight, and each edge has a 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 (\textit{Journal of Algorithms, 55:42-57, 2005}) gave an LP-rounding
$3$-approximation algorithm when edges have unit processing times. We give a
more efficient primal-dual algorithm that achieves the same approximation
guarantee. When edges have arbitrary processing times we
give a primal-dual 5.83-approximation algorithm. 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 \mbox{$\sqrt{2} \approx 1.414$}, thus
improving the
1.796-approximation given by Gandhi~\etal\ (\textit{ACM Transaction on
Algorithms, 2(1):116-129}, 2006). We show that the analysis of our algorithm is
almost tight.
