Maximum 4-block-free matrices and knapsack-type relaxations

Tibor Illés, Jakob Krarup

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)115-131
Number of pages17
JournalPure Mathematics and Applications
Volume10
Issue number2
Publication statusPublished - 31 Jan 1999
Externally publishedYes

Keywords

  • 4-block-free matrices
  • knapsack-type relaxations
  • maximum cardinality bipartile matching problem
  • MCBMP
  • greedy algorithm

Fingerprint

Dive into the research topics of 'Maximum 4-block-free matrices and knapsack-type relaxations'. Together they form a unique fingerprint.

Cite this