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

RIA：在线和动态算法：未来不确定的计算

• 批准号: 9409945
• 负责人: Stephen Tate
• 金额: $ 6.75万
• 依托单位: University of North Texas
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-07-15 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409945&HistoricalAwards=false
• 关键词: RIA; Line; Dynamic; Algorithms; Computing

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.

这个项目包括在线和动态算法的研究---算法类型的统一主题的不确定性对算法的未来要求。 新的平均情况下的分析方法引入到在线算法的研究，借鉴信息论和数据压缩（特别是，从随机复杂性）的经验。 此外，当输入请求是从一个已知的分布，作出最佳的在线决策的计算复杂性进行了研究。 在动态算法和数据结构领域，通过检查现有（或可能新的）并行算法的结构来开发用于设计动态算法的技术。 初步结果表明，如何使用易于计算的代数电路的属性，以设计动态算法，这些结果在这个项目中扩展到更广泛的一类问题，涉及更复杂的增量操作的输入。 此外，并行机的动态算法的开发，这是非常重要的应用程序，需要非常快速的响应动态变化的数据。