IJPAM: Volume 42, No. 2 (2008)

UNIFORM PAGE MIGRATION ON GENERAL NETWORKS

Akira Matsubayashi
Division of Electrical Engineering and Computer Science
Graduate School of Natural Science and Technology
Kanazawa University
Kakuma-Machi, Kanazawa, 920-1192, JAPAN
e-mail: mbayashi@t.kanazawa-u.ac.jp


Abstract.In this paper we consider the page migration problem in the uniform model. We give a $2+\sqrt{2}$-competitive deterministic online algorithm on general networks. We also show an improved lower bound of $3.1639$ for general networks and an explicit lower bound of $3.1213$ for ring networks.

Received: August 17, 2007

AMS Subject Classification: 90C35

Key Words and Phrases: page migration, data management, online algorithm

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 42
Issue: 2