Application of graph-theoretic approaches to the random landscapes of the three-dimensional assignment problem

作者：Kammerdiner Alla^*; Pasiliao Eduardo

来源：Optimization Letters, 2013, 7(1): 79-87.

DOI：10.1007/s11590-011-0396-x

• Fitness landscape
• Search algorithms
• Digraphs
• Spanning forests
• Laplacian matrix
• Eigenvalues
• Algebraic multiplicity

We study local optima of combinatorial optimization problems. We show that a local search algorithm can be represented as a digraph and apply recent results for spanning forests of a diagraph. We establish a correspondence between the number of local optima and the algebraic multiplicities of eigenvalues of digraph laplacians. We apply our finding to the three-dimensional assignment problem.

• 出版日期2013-1