×

An online algorithm optimally self-tuning to congestion for power management problems. (English) Zbl 1242.90060

Solis-Oba, Roberto (ed.) et al., Approximation and online algorithms. 9th international workshop, WAOA 2011, Saarbrücken, Germany, September 8–9, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-29115-9/pbk). Lecture Notes in Computer Science 7164, 35-48 (2012).
Summary: We consider the classical power management problem: There is a device which has two states ON and OFF and one has to develop a control algorithm for changing between these states as to minimize (energy) cost when given a sequence of service requests. Although an optimal 2-competitive algorithm exists, that algorithm does not have good performance in many practical situations, especially in case the device is not used frequently. To take the frequency of device usage into account, we construct an algorithm based on the concept of “slackness degree.” Then by relaxing the worst case competitive ratio of our online algorithm to \(2 + \epsilon \), where \(\epsilon \) is an arbitrary small constant, we make the algorithm flexible to slackness. The algorithm thus automatically tunes itself to slackness degree and gives better performance than the optimal 2-competitive algorithm for real world inputs. In addition to worst case competitive ratio analysis, a queueing model analysis is given and computer simulations are reported, confirming that the performance of the algorithm is high.
For the entire collection see [Zbl 1241.68041].

MSC:

90B22 Queues and service in operations research
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI