Variational Methods in Combinatorial Optimization and Phylogeny Reconstruction

Henrik Jönsson

    Research output: ThesisDoctoral Thesis (compilation)

    Abstract

    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.
    Original languageEnglish
    QualificationDoctor
    Awarding Institution
    Supervisors/Advisors
    • [unknown], [unknown], Supervisor, External person
    Award date2001 Dec 14
    Publisher
    ISBN (Print)91-7874-161-1
    Publication statusPublished - 2001

    Bibliographical note

    Defence details

    Date: 2001-12-14
    Time: 10:15
    Place: Lecture hall F, Department of Theoretical Physics

    External reviewer(s)

    Name: Monasson, Remi
    Title: [unknown]
    Affiliation: [unknown]

    ---

    Subject classification (UKÄ)

    • Biophysics

    Free keywords

    • statistical physics
    • gravitation
    • relativity
    • annealing
    • variational
    • mean-field
    • phylogeny
    • constraint satisfaction
    • combinatorial optimization
    • maximum likelihood
    • Physics
    • Fysik
    • Mathematical and general theoretical physics
    • quantum mechanics
    • classical mechanics
    • klassisk mekanik
    • kvantmekanik
    • relativitet
    • statistisk fysik
    • termodynamik
    • Fysicumarkivet A:2001:Jönsson
    • Matematisk och allmän teoretisk fysik
    • thermodynamics

    Fingerprint

    Dive into the research topics of 'Variational Methods in Combinatorial Optimization and Phylogeny Reconstruction'. Together they form a unique fingerprint.

    Cite this