Skip to content Skip to navigation
Computer Science Department Colloquium
10/22/2013 11:00 am
CoRE Lecture Hall (Room 101)

Hallucination Helps: Energy Efficient Virtual Circuit Routing

Kirk Pruhs, University of Pittsburgh

Faculty Host: Martin Farach-Colton

Abstract

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

Bio