Asymptotically Optimal Online Page Migration on Three Points

作者：Matsubayashi Akira^*

来源：Algorithmica, 2015, 71(4): 1035-1064.

DOI：10.1007/s00453-013-9841-9

• Page migration
• Work function algorithm
• Competitive analysis
• Server problem

This paper addresses the page migration problem: given online requests from nodes on a network for accessing a page stored in a node, output online migrations of the page. Serving a request costs the distance between the request and the page, and migrating the page costs the migration distance multiplied by the page size Da parts per thousand yen1. The objective is to minimize the total sum of service costs and migration costs. Black and Sleator conjectured that there exists a 3-competitive deterministic algorithm for every graph. Although the conjecture was disproved for the case D=1, whether or not an asymptotically (with respect to D) 3-competitive deterministic algorithm exists for every graph is still open. In fact, we did not know if there exists a 3-competitive deterministic algorithm for an extreme case of three nodes with Da parts per thousand yen2. As the first step toward an asymptotic version of the Black and Sleator conjecture, we present 3- and (3+1/D)-competitive algorithms on three nodes with D=2 and Da parts per thousand yen3, respectively, and a lower bound of 3+Omega(1/D) that is greater than 3 for every Da parts per thousand yen3. In addition to the results on three nodes, we also derive rho-competitiveness on complete graphs with edge-weights between 1 and 2-2/rho for any rho a parts per thousand yen3, extending the previous 3-competitive algorithm on uniform networks.

• 出版日期2015-4