Ivona Bezakova, Nayantara Bhatnagar, Eric Vigoda
Sampling Binary Contingency Tables with a Greedy Start

Abstract:  We study the problem of counting and randomly sampling binary contingency tables.  For given row and column sums, we are want to approximately count (or sample) n x m  matrices with entries in {0,1}with the specified row/column sums. Note that this is equivalent to the problem of counting or generating bipartite graphs with a given degree sequence. We present a simulated annealing algorithm with running time O((nm)² D³ d_max log⁵(n+m)) for any row or column sums where D is the sum of the row sums (which is equal to the sum of the column sums) and d_max is the maximum row or column sum. Previous work reduced the problem to computing the permanent, or restricted attention to row/column sums that are close to regular.  Our algorithm, by avoiding reduction to computing the permanent, achieves a better time bound. The interesting aspect of our simulated annealing algorithm is that it starts at a non-trivial instance, whose solution relies on the existence of short alternating paths in the graph constructed by a particular Greedy algorithm.