Concentration For Independent Permutations.

An extended version of a concentration inequality based on the work of Talagrand is presented. The given inequality concerns a family of independent random permutations. One particular use is for analyzing randomized methods for graph coloring that involve randomly relabelling the colors used in dif...

ver descrição completa

Detalhes bibliográficos
Autor principal: McDiarmid, C
Formato: Journal article
Idioma:English
Publicado em: 2002
Descrição
Resumo:An extended version of a concentration inequality based on the work of Talagrand is presented. The given inequality concerns a family of independent random permutations. One particular use is for analyzing randomized methods for graph coloring that involve randomly relabelling the colors used in different parts of the graph.