Output details

Palette-colouring: a belief propagation approach

<12> The prototype combinatorial optimization problem of graph colouring has strong links to constrained scheduling and computational optimization. This paper transforms it into a model for efficient information storage and retrieval on sparse random networks, and propose a new algorithm that correctly takes into account the many-body nature of the constraints. It significantly improves upon existing belief propagation approaches, and is applicable to other combinatorial optimization problems. The paper has sparked follow-up papers by other authors, and has contributed to a KTP with FactoryMaster on job-shop scheduling (£120k).