Computational bounds for local search in combinatorial optimization |
| |
Authors: | Yu A Kochetov |
| |
Institution: | (1) Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia |
| |
Abstract: | The results related to finding local optima in combinatorial optimization are overviewed. The class of polynomial-time local search problems (class PLS) is considered. By analogy with Cook’s theorem, the existence of most complicated problems in this class is established. The number of steps in local descent algorithms is estimated in the worst and average cases. The local search determination of exact and approximate solutions with guaranteed error bounds is discussed. |
| |
Keywords: | local search PLS-complete problems metaheuristics overview |
本文献已被 SpringerLink 等数据库收录! |
|