Algorithms for changing environments

点击翻译按钮获取中文摘要

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.