Marco	Pretti -	Politecnico di Torino	#	
Palette coloring: a belief-propagation approach	#
We have  considered a variation of the graph-coloring problem. The optimisation goal 
is to color the vertices of a graph with a fixed number of 
colours, in a way to maximise the number of different colors 
present in the set of nearest neighbors of each given vertex. 
This problem, which we have pictorially called 
"palette-coloring", has been recently addressed as a basic 
example of combinatorial optimization 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, whereas heuristics based on belief 
propagation turn out to exhibit noticeable performances.