Algorithms that handle change over time and space

处理随时间和空间变化的算法

• 批准号: RGPIN-2016-03621
• 负责人: Nishimura, Naomi
• 金额: $ 1.89万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708821
• 关键词: Algorithms; handle; change; over; time

My goal over the next five years is to understand how algorithms can be designed to accommodate change, where change can take place before, during, or after a problem is solved. Depending on when the change occurs, it might result in modifications to the original input or in multiple solutions to a single input. The type of change can be either inherent in or external to the problem and the inputs. The areas of parameterized complexity and reconfiguration lend themselves well to investigations of approaches to solving problems in such settings. As a real-life example, repairs to power stations might require change between two good placements of customers, placements in which the output of each station is sufficient to meet the needs of all customers it serves. To minimize disruption of service, customers are moved one by one, each change resulting in a good assignment. In general, reconfiguration models changes that occur after a problem has been solved; solutions to a specific input (here, good assignments) can be viewed as vertices in a reconfiguration graph, where an edge indicates that one solution can be transformed into another in a single step, for some definition of a step. Recent research results have considered various properties of the reconfiguration graph, such as connectivity and diameter, and include the problem of determining whether there is a path from solution S to solution T (known as S-T connectivity). A natural setting for the study of change is the framework of parameterized complexity. Here, one identifies parameters of a problem and attempts to develop an algorithm running in time polynomial in the size of the input but subject to a potentially larger function of the parameters. This approach can yield practical algorithms for otherwise intractable problems in situations when the parameters are small, or demonstrate that such algorithms are unlikely to exist. Parameters can measure how much inputs can differ, how much change can be allowed, or how much solutions can vary for cases in which change occurs before, during, or after a problem is solved, respectively. My recent results combine reconfiguration and parameterized complexity; here parameters under consideration include the length of the transformation from one solution into another, bounds on the sizes of solutions, and properties of the inputs. My two-fold approach to the study of change encompasses both general properties of classes of problems and results optimized for specific settings chosen from a wide spectrum of diverse application areas, such as fundamental problems with applications to biology, voting protocols, and communication and social networks. I plan to form a unified framework of models that captures change in both inputs and outputs. Examination of the parameterized complexity of such models may yield practical solutions to real-life problems as well as a general understanding about the nature of change.

我在未来五年的目标是理解如何设计算法来适应变化，其中变化可以在问题解决之前、期间或之后发生。根据更改发生的时间，它可能会导致对原始输入的修改或对单个输入的多个解决方案。改变的类型可以是问题和输入所固有的，也可以是外部的。参数化的复杂性和重新配置的领域非常适合于研究在这种环境下解决问题的方法。 作为现实生活中的一个例子，电站的维修可能需要在两个良好的客户位置之间进行转换，即每个电站的输出足以满足其服务的所有客户的需求。为了最大限度地减少服务中断，客户一个接一个地移动，每次更改都会产生一个好的任务。通常，重新配置对问题解决后发生的更改进行建模；特定输入的解决方案(在这里是良好的分配)可以被视为重新配置图中的顶点，其中的边表示可以在单个步骤中将一个解决方案转换为另一个解决方案，以对步骤进行某种定义。最近的研究结果考虑了重构图的各种性质，如连通性和直径，其中包括确定是否存在从S解到解T的路径(称为S-T连通性)的问题。 研究变化的一个自然环境是参数复杂性的框架。这里，人们识别问题的参数，并试图开发一种在输入大小的时间多项式中运行的算法，但受制于参数的潜在更大函数。这种方法可以在参数较小的情况下为原本难以解决的问题产生实用的算法，或者证明这样的算法不太可能存在。对于在问题解决之前、期间或之后发生更改的情况，参数可以测量输入可以有多大差异、允许有多少更改或解决方案可以有多大不同。我最近的结果结合了重新配置和参数化的复杂性；这里考虑的参数包括从一个解决方案到另一个解决方案的转换长度、解决方案大小的界限以及输入的属性。 我研究变化的两种方法既包括问题类别的一般属性，也包括针对从广泛的不同应用领域选择的特定设置进行优化的结果，例如应用于生物学、投票协议以及通信和社交网络的基本问题。我计划形成一个统一的模型框架，以捕获输入和输出中的变化。检查这些模型的参数复杂性可能会产生现实问题的实际解决方案，并对变化的性质有一个大致的理解。