Palette-colouring: a belief propagation approach

Pelizzola, Alessandro, Pretti, Marco and van Mourik, Jort (2011). Palette-colouring: a belief propagation approach. Journal of Statistical Mechanics, 2011 (5),

Abstract

We consider a variation of the prototype combinatorial optimization problem known as graph colouring. Our optimization goal is to colour the vertices of a graph with a fixed number of colours, in a way to maximize the number of different colours present in the set of nearest neighbours of each given vertex. This problem, which we pictorially call palette-colouring, has been recently addressed as a basic example of a problem arising in the context of distributed data storage. Even though it has not been proved to be NP-complete, random search algorithms find the problem hard to solve. Heuristics based on a naive belief propagation algorithm are observed to work quite well in certain conditions. In this paper, we build upon the mentioned result, working out the correct belief propagation algorithm, which needs to take into account the many-body nature of the constraints present in this problem. This method improves the naive belief propagation approach at the cost of increased computational effort. We also investigate the emergence of a satisfiable-to-unsatisfiable 'phase transition' as a function of the vertex mean degree, for different ensembles of sparse random graphs in the large size ('thermodynamic') limit.

Publication DOI: https://doi.org/10.1088/1742-5468/2011/05/P05010
Divisions: Engineering & Applied Sciences > Mathematics
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: ©2011 IOP Publishing Ltd.
Uncontrolled Keywords: cavity and replica method,optimization over networks,message-passing algorithms,Statistics and Probability,Statistical and Nonlinear Physics,Statistics, Probability and Uncertainty
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
Published Date: 2011-05
Authors: Pelizzola, Alessandro
Pretti, Marco
van Mourik, Jort

Download

[img]

Version: Published Version

| Preview

Export / Share Citation


Statistics

Additional statistics for this record