An online algorithm optimally self-tuning to congestion for power management problems (コンピュテーション)

概要

論文の詳細を見る
In this paper we consider a device which has two states and develop their control algorithm for changing ON and OFF each other. This problem is often called the power management problem. Although the optimal 2-competitive algorithm is known, this algorithm do not have good performance from the practical point of view, especially in the case that the device is not used frequently. To consider the frequency of device usage, we introduce a "slackness degree" and design online algorithms. By relaxing the worst case competitive ratio of our online algorithm to 2+ε, where ε is an arbitrary small constant, we make the algorithm flexible to slackness, i.e., it automatically tunes itself to every slackness-degree and gives for better performance.
2011-04-15