Arranging apples in an array
type: Item
instance of: scholarly article
title: Arranging apples in an array
zbMATH Open document ID: 0664.05012
DOI: 10.1007/BF01941133
author: Jens Clausen
author: Jakob Krarup
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 4085667
zbMATH Keywords: matrix of zeros and ones
zbMATH Keywords: greedy algorithm
MaRDI profile type: Publication
cites work: Uniformly distributed sums of Bernoulli variables
cites work: A theorem on flows in networks
cites work: Q3292914
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: Counting Binary Matrices with Given Row and Column Sums
cites work: Q3860734
cites work: Combinatorial Properties of Matrices of Zeros and Ones
cites work: On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
description: scientific article; zbMATH DE number 4085667