RIA: On-Line and Dynamic Algorithms: Computing with an Uncertain Future

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

This project involves the study of both on-line and dynamic algorithms---types of algorithms with the unifying theme of uncertainty about future requests to the algorithm. New methods of average-case analysis are introduce to the study of on-line algorithms, drawing from experience in information theory and data compression (and, in particular, from stochastic complexity). In addition, the computational complexity of making optimal on-line decisions when the input requests are drawn from a known distribution, is investigated. In the area of dynamic algorithms and data structures, techniques are developed for designing dynamic algorithms by examining the structure of existing (or perhaps new) parallel algorithms. Initial results show how to use easily computable properties of algebraic circuits in order to design dynamic algorithms, and these results are extended in this project to a wider class of problems involving more complex incremental operations on the inputs. In addition, dynamic algorithms for parallel machines are developed, which are important for applications which require very fast response to dynamically changing data.