Algorithms that handle change over time and space

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

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.