Arranging apples in an array
Given positive integers m and n together with integer sequences \(a=(a_ 1,a_ 2,...,a_ m)\) and \(b=(b_ 1,b_ 2,...,b_ n)\) satisfying \(0<a_ i<n\), \(0<b_ j<m\) for all i and j, and \(\sum a_ i=\sum b_ j,\) the problem is to find an \(m\times n\) matrix of zeros and ones such that \(\sum_{j}x_{ij}=a_ i\) and \(\sum_{i}x_{ij}=b_ j\) for all i and j. This is a well solved problem. This paper provides an overview and a synthesis of earlier results. A greedy algorithm developed from Ford-Fulkerson's approach is considered in depth. A new and simple proof of its correctness is presented. Finally a series of open questions is posed as suggestions for future research.
- The structure matrix and a generalization of Ryser's maximum term rank formula
- Realization of Matrices and Directed Graphs
- Discrepancy of matrices of zeros ond ones
- An algorithm for finding the number of (0, 1, 2,…, l)-matrices with prefixed row sum and column sum vectors
- Integral matrices with given row and column sums
- A theorem on flows in networks
- Combinatorial Properties of Matrices of Zeros and Ones
- Counting Binary Matrices with Given Row and Column Sums
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3662464 (Why is no real title available?)
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
- Uniformly distributed sums of Bernoulli variables
This page was built for publication: Arranging apples in an array
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115447)
