A Study of Reconfiguration Problems to Develop Dynamic Systems

在这项研究中，我们研究了在一个问题的两个可行解之间找到一个逐级变换的问题，使得所有中间结果也是可行的。特别地，我们研究了理论计算机科学中最基本的问题之一--背包问题，以及具有供需关系的图划分问题，该问题在输电网络中有一定的应用。我们首先分析了这些问题的计算难度，然后给出了近似算法。从逼近比的角度来看，我们的逼近算法是最有可能的。

In this research, we study problems of finding a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. In particular, we study such problems for knapsack problem, which is one of the most fundamental problems in theoretical computer science, and for graph partitioning problem with supply and demand, which has some applications to power delivery network. We first analyzed the computational hardness of these problems, and then gave approximationalgorithms. Our approximation algorithms are best possible from the viewpoint of approximation ratio.