In an online problem the input is revealed to the algorithm only one piece at a time, whereas an omniscient adversary knows the entire input in advance. How well can this online algorithm perform relative to the prescient adversary? Just how valuable is foresight? This is the central question in the study of online algorithms. This project will study online problems with the goals of constructing better online algorithms and of proving lower bounds on their performance. Specifically, one focus will be the study of server problems in which mobile servers move among the points of a metric space, serving requests, and in which the complexity measure is the total distance moved by the servers. Also, motion planning, layered graph traversal, coloring, scheduling, and list updates will be considered from the online perspective. Algorithmic questions related to genetics will also be studied.
