Algorithms for changing environments

适应不断变化的环境的算法

• 批准号: RGPIN-2022-02953
• 负责人: Nishimura, Naomi
• 金额: $ 2.55万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750221
• 关键词: Algorithms; 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.

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