Finding Many Sparse Cuts Using Entropy Maximization

Farshad Noravesh

A randomized algorithm for finding sparse cuts is given which is based on constructing a dual markov chain called multiscale rings process(MRP) and a new concept of entropy. It is…