Local Optima Approximation Scheme based on Combinatorial Local Search Algorithms

点击翻译按钮获取中文摘要

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.