ICS Theory Group

ICS 269, Spring 2006: Theory Seminar

Apr 28, 2006, in CS 243

Theoretical Models and Solutions for Problems in Computer Science

Presented by John Augustine


Several fundamental problems in computer science have elegant solutions. In many cases, the problems are modeled theoretically and the solutions are analyzed rigorously. We present our results in a manner that highlights this research process involved in solving computer science problems.

The problem of powering down is encountered when any energy intensive system goes through an idle period of time. Many systems are designed with different levels of sleep states that consume energy at different rates and have different power-up costs. We initiate this study by presenting several models that are increasingly more accurate in capturing the essence of the problem. Along with these models, we introduce the notion of competitive ratio, which is the theoretical framework for analyzing online algorithms and present an algorithm that is provably within a small error factor of the best possible competitive ratio.

We will conclude with a summary of other previous work and a plan for future research in collaboration with undergraduate students.