Abstract
A 0-1 matrix is called l-block-free if it nowhere has a pair of rows ancl a pair of columns such that the four entries thus singled out are all 1,s. What is the maximum number of 1's a 4-block-free matrix can have? We investigate a knapsack-type relaxation of a 0-1 prograrnming formulatiotr of the problcm, accotrnt for its solution properties ancl acldress issues as to t,he realizobility in terms of 0-1 matrices of the solutions found. We note frtrt,hermore that a conclusivc answer, valicl fclr all square rrratrices, would also settle the cla.ssical anrl gelrerally unanswered question as to ttle existence of a so-called finite projectiue plane of a given order. Along the way, some surprisingly simple proofs of earlier results arc provided. Also a nerv characlerization of a finite projective plane is given.
Original language | English |
---|---|
Pages (from-to) | 115-131 |
Number of pages | 17 |
Journal | Pure Mathematics and Applications |
Volume | 10 |
Issue number | 2 |
Publication status | Published - 31 Jan 1999 |
Externally published | Yes |
Keywords
- 4-block-free matrices
- knapsack-type relaxations
- maximum cardinality bipartile matching problem
- MCBMP
- greedy algorithm