Online Algorithms

点击翻译按钮获取中文摘要

Online computation involves optimization problems for which the input isrevealed progressively. Online algorithms base their decisions only on thepast without knowledge of the future, much in the same way that a stockmarket investor or a robot that explores an unknown environment decideabout their next action. Naturally such problems of decision-making withincomplete information arise in many areas. During the last decaderesearch in the area of online algorithms has been very intensive. Still,some of the fundamental problems remain unresolved and important problemsarise from new applications. The project deals both with old and newonline problems.Perhaps the most important fundamental unsolved problem is the k-serverproblem. The objective is to settle the k-server conjecture and toinvestigate other variants of the problem such as the k-taxicab problemand the CNN problem. Another objective is to design and analyzecompetitive algorithms for a related problem, the online matching problemon Euclidean spaces; some interesting variants of the problem seem to playa central role in new e-commerce applications. For all these and manyother problems, one algorithm, the generalized Work Function Algorithm,seems to have almost optimal competitive ratio. The research addresses theroots of this phenomenon.Research deals also with the pertinent problem of indexing of databases;the size of datasets of real applications has been increasing dramaticallyand so does the importance of good indexing schemes. Competitive analysiscan be used to quantify how much the performance of indexing schemes isaffected by changes in a database. Finally, the techniques of competitiveanalysis are a useful tool to address specific game-theoretic problems innetworks.