2011/04/02 by Jeffrey W. Miller, Miller, Jeffrey W., Matthew Tom Harrison +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Computation (stat.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1104.0323
openalex publication_date 2011/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe a dynamic programming algorithm for exact counting and exact uniform sampling of matrices with specified row and column sums. The algorithm runs in polynomial time when the column sums are bounded. Binary or non-negative integer matrices are handled. The method is distinguished by applicability to non-regular margins, tractability on large matrices, and the capacity for exact sampling.