The Multilevel Splitting algorithm for graph colouring with application to the Potts model
Date
2017
Authors
Vaisman, R.
Roughan, M.
Kroese, D.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Philosophical Magazine, 2017; 97(19):1646-1673
Statement of Responsibility
Radislav Vaisman, Matthew Roughan and Dirk P. Kroese
Conference Name
Abstract
Calculating the partition function of the zero-temperature antiferromagnetic model is an important problem in statistical physics. However, an exact calculation is hard since it is strongly connected to a fundamental combinatorial problem of counting proper vertex colourings in undirected graphs, for which an efficient algorithm is not known to exist. Thus, one has to rely on approximation techniques. In this paper, we formulate the problem of the partition function approximation in terms of rareevent probability estimation and investigate the performance of a particle-based algorithm, called Multilevel Splitting, for handling this setting. The proposed method enjoys a provable probabilistic performance guarantee and our numerical study indicates that this algorithm is capable of delivering accurate results using a relatively modest amount of computational resources.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2017 Informa UK Limited, trading as Taylor & Francis Group