Algorithms that handle change over time and space

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

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