Local Optima Approximation Scheme based on Combinatorial Local Search Algorithms

已知许多有用的组合优化问题是NP难的，这意味着这些问题很难（或可能不可能）在合理的计算时间内找到保证（接近）最优的解决方案。另一方面，尽管困难，元分析算法被称为找到“实际上”好的解决方案（不一定在合理的计算时间。在本研究中，我们从“理论”的角度研究了局部搜索型元认知。我们得到了几个结果：（1）图优化问题的（局部搜索型）近似算法的设计与分析，（2）图优化问题的重构问题的计算复杂性，（3）图优化问题的再优化的计算复杂性。

Many useful combinatorial optimization problems are known to be NP-hard, which means that these problems are difficult (or probably impossible) to find solutions guaranteed to be (near-)optimal in reasonable computational time. On the other hand, in spite of the difficulty, metaheuristics algorithms are known to find "practically" good solutions (not necessarily in reasonable computational time. In this study, we investigated local-search type meta-heuristics from the "theoretical" viewpoints. We obtain several results:(1) Design and analysis of (local-search type) approximation algorithms for graph optimization problems, (2) Computational complexity of the reconfiguration problems for graph optimization problems, (3) Computational complexity of the reoptimization of graph optimization problems.