Variational Methods in Combinatorial Optimization and Phylogeny Reconstruction

Sammanfattning: Algorithms based on the variational approach, as used in statistical physics, are developed. For constraint satisfaction problems a novel cost function, based on information-theoretic arguments, is introduced, and an algorithm similar to the mean-field annealing algorithm is proposed. It outperforms the conventional mean-field algorithm, and its performance is comparable to good problem-dedicated heuristics for KSAT and graph coloring. For nonlinear assignment problems, improvements to mean-field annealing algorithms based on Potts spins are suggested, and confirmed for TSP. Also a more proper variational approach to assignment problems is proposed and analysed. A novel variational approximation to maximum likelihood is introduced and applied to phylogeny reconstruction. In tests on artificial and real DNA-sequences, the performance is seen to be comparable to that of standard maximum likelihood for reasonably similar sequences.