Presentation	2005-01-19 A Competitive Online Algorithm for Data Migration on Rings Ryosuke ITO, Akira MATSUBAYASHI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Data migration problem is, given a network G, a node a_0 of G which holds a data x of size D initially, and a sequence s_1, ..., s_k of nodes which issue requests for accessing x, to compute a sequence a_1, ..., a_k of nodes to hold x so that Σ^k_(d(a_, s_i)+D・d(a_, a_i)) is minimized, where d(u, v) is the distance between two nodes u and v. There have been reported a number of online algorithm for the data migration problem, such as a 4.086-competitive algorithm on arbitrary weighted networks, a 3-competitive algorithm on weighted trees, a 3-competitive algorithm on uniform networks, and a (2+1/(2D))-competitive algorithm on continuous trees. In this report, we show a 3.791-competitive algorithm on continuous rings for the case that D=1.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	ring / data migration / online algorithm / competitive ratio
Paper #	CAS2004-62
Date of Issue

Conference Information
Committee	CAS
Conference Date	2005/1/12(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Circuits and Systems (CAS)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A Competitive Online Algorithm for Data Migration on Rings
Sub Title (in English)
Keyword(1)	ring
Keyword(2)	data migration
Keyword(3)	online algorithm
Keyword(4)	competitive ratio
1st Author's Name	Ryosuke ITO
1st Author's Affiliation	Division of Electronics and Computer Science, Kanazawa University()
2nd Author's Name	Akira MATSUBAYASHI
2nd Author's Affiliation	Division of Electrical Engineering and Computer Science, Kanazawa University
Date	2005-01-19
Paper #	CAS2004-62
Volume (vol)	vol.104
Number (no)	555
Page	pp.pp.-
#Pages	5
Date of Issue