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

动态规划是算法设计和分析中最基本、最系统的技术之一。由Richard Bellman在20世纪40年代开创，用于工程控制理论的应用，这种方法在计算机科学，应用数学，工程，生物学和经济学中的各种优化问题中非常受欢迎。然而，动态规划算法通常具有高多项式时间复杂度（二次、三次或更高）以及高空间要求。这大大限制了该方法的实用性。动态编程之类的通用工具在可扩展性方面的任何进步都可能对不同领域产生巨大影响。在过去的几十年里，人们在加速动态编程方面做出了重大努力;然而，加速增益大多仅限于最多的多对数因子改进（例如，四个俄罗斯人的方法）。这种限制主要是由于专注于开发精确的最佳算法。另一方面，在许多应用中，人们可能会放松对最优性的需求，而是解决近似解。允许即使是一个小的次最优可能会导致一个巨大的利益，在时间和空间的requirements.The主要动机，这个项目是引入新的技术，开发高度可扩展的动态规划方法，作为一个通用的工具包，设计可扩展的算法。了解近似性和时间复杂度之间的权衡仍然是一个主要目标。为了实现这一目标，将需要一套新的数学工具，因为现有的方法大多只给出时间复杂度的多对数改进，或者只能处理数据满足附加局部属性的情况。随机化将在该项目中发挥关键作用。各种随机素描方法和压缩技术将被考虑，结合新的工具，从信息论，图论和概率方法。虽然主要重点是改善运行时间，但在本项目下制定的方法也将对减少空间使用产生直接影响。最后，本文将研究序列上的调度和模式识别中的一类基本问题，这些问题不仅具有理论意义，而且在大规模数据管理、生物信息学和可持续计算等领域具有广泛的应用前景，对大数据领域中的重大优化问题的可扩展算法设计具有重要意义.这些算法将在生物信息学、工业云集群使用数据、动态网络路由数据等各种公开数据集上实施和测试。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.