I will start by giving my giving my view of the current state of the art
of the theory of energy as a computational resource.
I will discuss some recent research that is fairly representative of the type of
green computing research that algortihmists are doing, namely on energy efficient circuit routing
protocols for a network of components that are speed scalable, and that may be shutdown when idle.
I will initially concentrate on the case that the power management components are links.
I will give a polynomial-time offline algorithm that has a poly-log approximation ratio.
This algorithm is a combination of three natural combinatorial algorithms.
The key step of the algorithm design is a random sampling technique that we call hallucination.
The algorithm extends rather naturally to an online algorithm.
The analysis of the online algorithm introduces a natural ``priority'' multicommodity flow problem,
and bounds the priority multicommodity flow-cut gap.
I will then briefly explain the additional difficulty faced if the power management components are vertices,
and explain how to how to surmount this difficulty in the offline case.
Collaborators: Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan,
Kirk Pruhs, Cliff Stein