Finding a Hamiltonian Cycle by minimizing a determinant
Michael Haythorpe, Walter Murray · arXiv (Cornell University) · 2015
It has been shown that the global minimizer of a smooth determinant of a matrix function reveals the largest cycle of a graph. When it exists this is a Hamiltonian cycle. Finding global minimizers even of a smooth function is a challenge. The difficulty is often exacerbated by the existence of many global minimizers. One may think this would help but in the case of Hamiltonian cycles the ratio of the number of global minimizers to the number of local minimizers is typically astronomically small. We describe efficient algorithms that seek to find global minimizers. There are various equivalent forms of the problem and here we describe the experience of two. The matrix function contains a matrix P(x), where x are the variables of the problem. P(x) may be constrained to be stochastic or doubly stochastic. More constraints help reduce the search space but complicate the definition of a basis for the null space. Even so we derive a definition of the null space basis for the doubly stochastic case that is as sparse as the constraint matrix and contains elements that are either 1, -1 or 0. Such constraints arise in other problems such as forms of the quadratic assignment problem.