CaltechAUTHORS
  A Caltech Library Service

Optimal Power-Down Strategies

Augustine, John and Irani, Sandy and Swamy, Chaitanya (2008) Optimal Power-Down Strategies. SIAM Journal on Computing, 37 (5). pp. 1499-1516. ISSN 0097-5397. https://resolver.caltech.edu/CaltechAUTHORS:AUGsiamjc08

[img]
Preview
PDF
See Usage Policy.

224Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:AUGsiamjc08

Abstract

We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case, in which there is a single active and a single sleep state, is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power-consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of $3 + 2\sqrt{2} \approx 5.828$ for any system.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/05063787XDOIUNSPECIFIED
Additional Information:©2008 Society for Industrial and Applied Mathematics. Received by the editors August 10, 2005; accepted for publication (in revised form) October 10, 2007; published electronically January 30, 2008. This author’s [J.A.] research was supported partially by NSF grants CCR-0105498 and CCF-0514082 and by ONR Award N00014-00-1-0617. This author’s [S.I.] research was supported partially by NSF grants CCR-0105498 and CCF-0514082 and by ONR Award N00014-00-1-0617. This author’s [C.S.] research was supported partially by NSF grant CCR-9912422.
Subject Keywords:online algorithms; power-aware computation; dynamic power management
Issue or Number:5
Record Number:CaltechAUTHORS:AUGsiamjc08
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:AUGsiamjc08
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10099
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:13 Apr 2008
Last Modified:03 Oct 2019 00:06

Repository Staff Only: item control page