Algorithms for changing environments

尽管已经开发了无数的算法来解决各种各样的问题，但很少有算法是为了适应变化而设计的。 我的研究项目的目标是利用理论与实践之间的协同作用，形成实用的算法，解决不断变化的环境中出现的各种现实问题。例如，考虑将客户分配给发电站;如果每个发电站都有足够的容量来满足分配给它的所有客户的需求，则分配是可行的。要重新安排客户从一个可行的分配更改为另一个可行的分配而不关闭整个系统，可以逐个移动客户，始终确保移动导致可行的分配。 这样，在发生变化的同时，力量可以继续流动。仅仅在十年前引入的重新配置框架是开发算法的自然方法，因为它可以通过重新配置步骤序列（例如将单个客户从一个发电站重新分配到另一个）来用于在配置（例如可行的分配）之间导航。 然而，到目前为止的研究，重构不能表达许多现实世界的问题的复杂性。此外，即使对于那些可以使用框架表达的问题，例如研究将生物分子划分和折叠成2D和3D结构的影响，有效的算法也是难以捉摸的;因此，重新配置一直未得到充分利用。为了将重构应用到真实的问题中，我的目标是：（1）丰富重构的表达能力;以及（3）开发工具包以将重新配置应用于各种问题，诸如无线网络中的通信、代码的有效存储以及用于量子模拟的原子的重新布置，与计算机科学各个领域的专家合作，包括算法设计，数据库和高性能计算，以及数学家，工程师和物理学家。 由于其新颖性和广泛的适用性，重新配置是一个有吸引力的领域，为学生在各个层次。第一次尝试研究的本科生可以很快熟悉重构的研究领域，开始做出原创性的贡献;研究生可以在重构的新分支上开始工作，为他们未来的研究和职业生涯奠定基础。建立桥梁，以其他研究领域的学生准备不同的职业生涯，因为他们学习的好处，形成一个网络，独立工作，并与他人合作，并沟通的想法，一个异质的观众。通过学习如何制定新的问题，与他人合作找到解决方案，并与不同领域的专家进行咨询，学生将为学术界或任何工作场所的职业生涯做好充分准备，其中环境会发生变化。

Although countless algorithms have been developed to solve a large variety of problems, few are designed to adapt to change.  The goal of my research program is to harness the synergy between theory and practice to form practical algorithms addressing a wide variety of real-life problems arising in changing environments. As an example, consider the assignment of customers to power stations; an assignment is workable if each power station has sufficient capacity to meet the demands of all of the customers assigned to it. To rearrange customers to change from one workable assignment to another without shutting down the entire system, customers can be moved one by one, always ensuring that a move results in a workable assignment.  In this way, power can continue to flow while changes are taking place. Introduced only a decade ago, the reconfiguration framework is a natural approach for developing algorithms, as it can be used to navigate among configurations (such as workable assignments) by means of a reconfiguration sequence of steps (such as the reassignment of a single customer from one power station to another).  However, as studied thus far, reconfiguration cannot express the intricacies of many real-world problems. Moreover, even for those problems that can be expressed using the framework, such as studying the effects of gerrymandering and folding biomolecules into 2D and 3D structures, efficient algorithms are elusive; thus, reconfiguration has been under-utilized. In order to apply reconfiguration to real problems, my objectives are to (1) enrich the expressive power of reconfiguration; (2) extend the range of types of algorithms developed; and (3) develop a toolkit to apply reconfiguration to diverse problems, such as communication in a wireless network, efficient storage of code, and the rearrangement of atoms for use in quantum simulation, in collaboration with experts in various areas of computer science, including algorithm design, databases, and high-performance computing, as well as mathematicians, engineers, and physicists. Due to its newness and wide applicability, reconfiguration is an attractive area for students at all levels. An undergraduate student attempting research for the first time can quickly become sufficiently familiar with the research area of reconfiguration to start making original contributions; a graduate student can initiate work on a new branch of reconfiguration forming the foundations of their future research and career. Building bridges to other fields of study prepares students for diverse careers, as they learn the benefits of forming a network, working independently and in collaboration with others, and communicating ideas to a heterogeneous audience. By learning how to formulate new problems, work with others to find solutions, and consult with experts in diverse fields, students will be well prepared for careers in academia or any workplace in which environments are subject to change.