Design and Analysis of Data Structures and Combinatorial Algorithms

这个项目是多年努力的继续，目的是发现和理解有效的数据结构、组合算法以及两者之间的关系。重点放在研究基本的、长期存在的和/或具有重大现实重要性的问题上。所寻求的不仅是具体的算法结果，还包括设计和分析的一般原则。具体来说，该项目的目标包括：(1)设计特定的算法和数据结构，从而更有效地解决重要的组合问题；(2)研究新的和旧的方法的最坏情况和典型情况的性能，以便能够预测给定情况下的最佳方法；(3)开发用于设计和分析的通用工具和原则，并在构造新的算法和数据结构时系统地应用这些工具和原则。渐近效率并不是唯一的目标；人们寻求的方法除了效率外，还表现出简单甚至优雅。当找到了一种既在理论上有效又在实践中可用的方法时，就取得了成功。我们的目标不仅是设计新的方法，而且要更深入地了解旧的方法，以便所有解决方案都可以精简到其本质，从而实现更高的效率和更高的简单性。

This project is a continuation of a multi-year effort to discover and understand efficient data structures, combinatorial algorithms, and the relationships between the two. The emphasis is placed on studying problems that are fundamental, longstanding, and/or of significant practical importance. Sought are not only specific algorithmic results, but also general principles of design and analysis. In particular, the goals of the project include: (1) to devise specific algorithms and data structures that result in more efficient solutions of important combinatorial problems; (2) to study the worst-case and typical-case performance of new and older methods, to allow prediction of the best method for a given situation; (3) to develop general tools and principles for design and analysis, and apply these tools and principles systematically in the construction of new algorithms and data structures. Asymptotic efficiency is not the only goal; methods are sought that display simplicity and even elegance in addition to efficiency. Success is achieved when a method is found that is both theoretically efficient and usable in practice. The objective is not only to devise new methods, but to gain greater insights into old ones, so that all solutions can be stripped down to their essence, achieving both greater efficiency and greater simplicity.***