Online Algorithms

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Online computation involves optimization problems for which the input is revealed progressively. Online algorithms base their decisions only on the past without knowledge of the future, much in the same way that a stock market investor or a robot that explores an unknown environment decide about their next action. Naturally such problems of decision-making with incomplete information arise in many areas. During the last decade research in the area of online algorithms has been very intensive. Still, some of the fundamental problems remain unresolved and important problems arise from new applications. The project deals both with old and new online problems. Perhaps the most important fundamental unsolved problem is the k-server problem. The objective is to settle the k-server conjecture and to investigate other variants of the problem such as the k-taxicab problem and the CNN problem. Another objective is to design and analyze competitive algorithms for a related problem, the online matching problem on Euclidean spaces; some interesting variants of the problem seem to play a central role in new e-commerce applications. For all these and many other problems, one algorithm, the generalized Work Function Algorithm, seems to have almost optimal competitive ratio. The research addresses the roots of this phenomenon. Research deals also with the pertinent problem of indexing of databases; the size of datasets of real applications has been increasing dramatically and so does the importance of good indexing schemes. Competitive analysis can be used to quantify how much the performance of indexing schemes is affected by changes in a database. Finally, the techniques of competitive analysis are a useful tool to address specific game-theoretic problems in networks.