CRII:AF: Scaling up Dynamic Programming for Certain Optimization Problems

动态规划是算法设计和分析中最基本、最系统的技术之一。该方法由Richard Bellman于20世纪40年代首创，用于工程控制理论的应用，此后在计算机科学，应用数学，工程，生物学和经济学的各种优化问题中非常受欢迎。然而，动态规划算法通常具有很高的多项式时间复杂度——二次、三次甚至更多——并且对空间的要求也很高。这极大地限制了该方法的实用性。动态规划等通用工具在可伸缩性方面的任何进步都可能对不同领域产生巨大影响。在过去的几十年里，在加速动态规划方面已经做出了重大的努力；然而，加速收益大多仅限于多对数因子的改进（例如，四俄罗斯方法）。这种限制主要是由于专注于开发精确的最优算法。另一方面，在许多应用程序中，人们可以放松对最优性的需求，而是满足于近似解决方案。即使允许很小的次优性也可能在时间和空间需求方面带来巨大的好处。该项目的主要动机是引入新技术来开发高度可扩展的动态规划方法，作为设计可扩展算法的通用工具包。理解近似性和时间复杂性之间的权衡仍然是一个主要目标。为了实现这一目标，将需要一套新的数学工具，因为现有的方法大多只能在时间复杂度上提供多对数改进，或者只能处理数据满足其他局部属性的情况。随机化将在这个项目中发挥至关重要的作用。将考虑各种随机素描方法和压缩技术，结合信息论，图论和概率方法的新工具。虽然主要的重点是改善运行时间，但在这个项目下开发的方法也将对减少空间使用产生直接影响。最后，我们将研究序列调度和模式识别中的一类基本问题，这些问题不仅具有理论意义，而且在大规模数据管理、生物信息学和可持续计算中具有广泛的应用。所提出的工作将显著提高大数据领域中出现的主要优化问题的可扩展算法设计的最新水平。这些算法将在生物信息学、工业云集群使用数据、动态网络路由数据等各种公开可用的数据集上实施和测试。PI与工业界的密切联系将导致与从业人员的合作，并在可能的情况下对开发的方法进行调整。PI在指导少数民族学生方面有经验，并致力于在研究生和本科阶段参与代表性不足的少数民族的前沿研究。

Dynamic programming is one of the most fundamental and systematic techniques for algorithm design and analysis. Pioneered by Richard Bellman in 1940s for applications in engineering control theory, this method has since been extremely popular in a huge variety of optimization problems in computer science, applied mathematics, engineering, biology and economics. However, dynamic programming algorithms typically have high polynomial time complexity--quadratic, cubic or even more--and high space requirements as well. This significantly limits the practicality of this method. Any advancement in the scalability of a generic tool like dynamic programming is likely to have a huge impact across different fields.There has been a significant effort in accelerating dynamic programming over the last several decades; however, the speedup gains have mostly been limited to only a poly-logarithmic factor improvement at best (e.g., the Four Russians Method). This limitation is primarily due to the focus on developing exact optimal algorithms. On the other hand, there are many applications where one may relax the need for optimality, and instead settle for an approximate solution. Allowing even a small suboptimality may lead to a huge benefit in time and space requirements.The principal motivation for this project is to introduce new techniques to develop highly scalable dynamic programming methodology as a generic toolkit for designing scalable algorithms. Understanding the tradeoff between approximability and time complexity remains a major goal. To achieve this goal, a new suite of mathematical tools will be required since existing methods mostly give only a poly-logarithmic improvement in time complexity, or can handle only the case when data satisfies additional local properties. Randomization will play a crucial role in this project. Various randomized sketching methods and compression techniques will be considered, incorporating fresh tools from information theory, graph theory, and the probabilistic method. While the major focus is on improving running time, the approaches developed under this project will have a direct effect in reducing space usage as well. Finally, a class of basic problems in scheduling and pattern recognition over sequences will be studied, which are not only of theoretical interest, but also have wide application in large scale data management, bioinformatics, and sustainable computing.The proposed work will significantly improve the state of the art in the design of scalable algorithms for major optimization problems arising in Big Data domains. The algorithms will be implemented and tested on a variety of publicly available data sets in bioinformatics, industrial cloud cluster usage data, dynamic network routing data, etc. The close connection of the PI with industry will result in collaborations with practitioners and possible adaptations of the developed methodologies when possible. The PI has experience in mentoring minority students and is committed to involvement of under-represented minorities, at both graduate and undergraduate levels, in cutting edge research.