Skip to main content
3 of 4
edited title
Masood
  • 169
  • 6

Selecting columns of a set of boolean matrices with constraint on the ones in each row

I've come up with the following question in my research: given a set $S$ of matrices with elements 0 or 1. Let $n_i$ be the total number of 1's in the $i$th row of all matrices in $S$. We want to select one column of each matrix, such that for the $i$th row, at least $\lfloor \alpha n_i \rfloor $ of the ones in that row are selected. Is there any $\alpha>0$ that we can guarantee the existence of such selection? In particular, what is the maximum $\alpha$ that we can guarantee? Is there a previous well known result about this problem?

Thanks.

Masood
  • 169
  • 6