TY - JOUR

T1 - Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

AU - Gandhi, Rajiv

AU - Mestre, Julián

N1 - Funding Information:
Research of R. Gandhi partially supported by Rutgers University Research Council Grant.
Funding Information:
Research of J. Mestre done at the University of Maryland; supported by NSF Awards CCR-0113192 and CCF-0430650, and the University of Maryland Dean’s Dissertation Fellowship.

PY - 2009/5

Y1 - 2009/5

N2 - 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 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 (J. 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 sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of √2\1.414 , thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. Algorithms 2(1), 116-129, 2006). We show that the analysis of our algorithm is almost tight.

AB - 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 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 (J. 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 sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of √2\1.414 , thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. Algorithms 2(1), 116-129, 2006). We show that the analysis of our algorithm is almost tight.

KW - Approximation algorithms

KW - Min-sum scheduling problems

KW - Primal-dual algorithms

UR - http://www.scopus.com/inward/record.url?scp=64949177985&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64949177985&partnerID=8YFLogxK

U2 - 10.1007/s00453-007-9118-2

DO - 10.1007/s00453-007-9118-2

M3 - Article

AN - SCOPUS:64949177985

SN - 0178-4617

VL - 54

SP - 54

EP - 71

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -