In online algorithms, we study problems where requests arrive in an online fashion. Each request must be processed without knowledge of the future. Our goal is to develop algorithms which perform well even with this uncertainty.
An example problem is that of renting skis. Suppose you are about to go skiing for the first time in your life, and suppose renting skis costs $30 while buying skis costs $600. Should you rent or should you buy? If you knew how many times you would go skiing in the future (ignoring issues such as inflation, wear and tear, and upgrading equipment), then your choice would be obvious. If you would go skiing less than 20 times, you should rent. If you would go skiing at least 20 times, then you should buy immediately. Of course, you do not know the future, and you must choose whether or not to rent or buy each time you go skiing until you finally decide to buy.
What is an optimal strategy for this problem? We typically model online algorithms as games being played against an all-knowing adversary. The ski rental adversary plays by the following rules. Each time you decide to rent, you will love the skiing and thus decide to go again. When you finally decide to buy skis, you immediately break your leg and can never go skiing again. What is your cost in this case? Suppose you went skiing j times breaking your leg after the jth trip. Then your total cost is 30j + 600. On the other hand, the optimal strategy would have been to either buy initially or rent all j times incurring an optimal cost of min(30j, 600). How much worse than optimal could you be? Your cost is at least twice that of optimal, and the following strategy guarantees that your cost is no more than twice optimal. Rent skis for the first 20 trips and then buy skis.
This is the type of analysis we engage in online algorithms. Of course, this case is fairly simple, and most of the analyses we carry out are far more sophisticated. I have concentrated mostly on scheduling and paging problems in the past, but others carry out research in such diverse fields as graph theory and financial portfolio management.
Selected Online Algorithm Publications
In scheduling problems, we are concerned with issues such as how to allocate a scarce resource such as processing time to a collection of jobs. Most of the scheduling problems I have worked on are also online problems in that the jobs arrive over time and may or may not need to be scheduled immediately before future jobs arrive. Furthermore, we have no knowledge of even the existence of future jobs when making our decisions.
One particular technique that I am interested in is that of resource augmentation. This was a technique popularized by Bala Kalyanasundaram and Kirk Pruhs where an online algorithm is given extra resources compared to an offline adversary in order to compensate for lack of knowledge of the future. This is often needed because traditional worst-case analysis of online algorithms often yields pessimistic results that offer little insight into how algorithms perform in practice.
Selected Scheduling Publications
My newest interest area is computational biology. I am a founding member of the Center for Biological Modeling at Michigan State University. We are interested in applying modeling techniques to biological problems. My specific interests are as follows.
First, I am interested in the development and analysis of algorithms for processing biological information. Example problems include that of taking a set of biological sequences and trying to reconstruct a phylogenetic tree from those sequences that explains the evolutionary history of these sequences. I am currently engaged in a research project with Charles Ofria and Thomas Schmidt where we plan to study how well various algorithms work on sequences generated by experiments with the Avida digital life system. I have also collaborated with James Cole in the Center for Microbial Ecology at MSU on the development of software for incrementally updating a phylogenetic tree.