Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Gandhi, Rajiv
Mestre, Julián

dblp
dblp

Not MPG Author(s):

Gandhi, Rajiv

BibTeX cite key*:

journal/algo/GandhiM2007

Title

Title*:

Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://www.springerlink.com/content/100117/

Download URL
for the article:

http://www.springerlink.com/content/7626hqk810344n01/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer.com

Publisher's
Address:

New York, NY

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

54

Number:

1

Publishing Date:

November 2009

Pages*:

54-71

Number of
VG Pages:


Page Start:

54

Page End:

71

Sequence Number:


DOI:

10.1007/s00453-007-9118-2

Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:

Primal-dual algorithms - Approximation algorithms - Min-sum scheduling problems

HyperLinks / References / URLs:


Copyright Message:

Springer Open Access

Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{journal/algo/GandhiM2007,
AUTHOR = {Gandhi, Rajiv and Mestre, Juli{\'a}n},
TITLE = {Combinatorial Algorithms for Data Migration to Minimize Average Completion Time},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2009},
NUMBER = {1},
VOLUME = {54},
PAGES = {54--71},
ADDRESS = {New York, NY},
MONTH = {November},
ISBN = {0178-4617},
DOI = {10.1007/s00453-007-9118-2},
}


Entry last modified by Anja Becker, 03/05/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
06/04/2008 02:32:15 PM
Revisions
9.
8.
7.
6.
5.
Editor(s)
Anja Becker
Anja Becker
Julian Mestre
Julian Mestre
Julian Mestre
Edit Dates
05.03.2010 14:59:36
05.03.2010 14:56:30
01/08/2010 04:50:57 PM
02/16/2009 09:38:24 AM
02/16/2009 09:34:24 AM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section