Conference paper
Improved approximation algorithms for broadcast scheduling
Nikhil Bansal, Don Coppersmith, et al.
SODA 2006
We present an upper bound O(n2) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process.
Nikhil Bansal, Don Coppersmith, et al.
SODA 2006
Don Coppersmith, Michel Petitjean
Comptes Rendus Mathematique
Don Coppersmith
IEEE Trans. Inf. Theory
Don Coppersmith, David Gamarnik, et al.
Random Structures and Algorithms