Algorithms that handle change over time and space

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

• 批准号: RGPIN-2016-03621
• 负责人: Nishimura, Naomi
• 金额: $ 1.89万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=660980
• 关键词: 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 连接性）的问题。 ***研究变化的自然环境是参数化复杂性框架。在这里，人们识别问题的参数，并尝试开发一种算法，该算法以输入大小的时间多项式运行，但受参数的潜在更大函数的影响。当参数很小时，这种方法可以产生解决其他棘手问题的实用算法，或者证明这种算法不太可能存在。参数可以分别测量在问题解决之前、期间或之后发生变化的情况下，输入可以有多少差异、可以允许有多少变化，或者解决方案可以有多少变化。我最近的结果结合了重新配置和参数化复杂性；这里考虑的参数包括从一种解决方案转换为另一种解决方案的长度、解决方案大小的界限以及输入的属性。***我研究变化的双重方法既包括问题类别的一般属性，也包括针对从广泛的不同应用领域中选择的特定设置进行优化的结果，例如生物学应用的基本问题、投票协议以及通信和社交网络。我计划形成一个统一的模型框架，捕获输入和输出的变化。对此类模型的参数化复杂性的检查可能会产生现实生活问题的实用解决方案以及对变化本质的一般理解。