Placing markers in grid and minimize similarity of rows

Question

Imagine a game on a grid of $m$ rows and $n$ columns. Player One will place a fixed number $r$ of markers in each row. Player Two will select the two rows which maximize the number of columns having markers in both rows, while Player One will try to minimize this number.

Example:

• $m = 3$
• $n = 3$
• $r = 2$

(a $3\times 3$ grid, placing 2 markers in each row)

First, Player One chooses two columns in each row, and places markers in those cells:

$$ \begin{array}{|c|c|c|} \hline X&X&\\ \hline X&X&\\ \hline &X&X\\ \hline \end{array} $$

Player Two then checks the row pairs $(1,2),(1,3)$ and $(2,3)$. The first pair shares 2 columns, and the last two pairs share only 1 column, so Player Two selects rows 1 and 2 because they have the most matching columns (2).

I am looking for a general strategy for placing markers given $(m,n,r)$. The strategy need not be optimal as it is intended to be uses in stochastic local search. This problem arises as a sub problem in investment design in finance. An easy to calculate lower bound exist, and for almost all instances I have seen a solution where the similarity is this lower bound exist.

Example instances: $(10,30,9)$ has lower bound 2. $(11,22,10)$ has lower bound 4.

The instance $(10,8,3)$ has a lower bound of 2 with the following solution: $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline X&X&X&&&&&\\ \hline X&X&&X&&&&\\ \hline X&X&&&X&&&\\ \hline X&X&&&&X&&\\ \hline X&X&&&&&X&\\ \hline X&X&&&&&&X\\ \hline X&&X&X&&&&\\ \hline X&&X&&X&&&\\ \hline X&&X&&&X&&\\ \hline X&&X&&&&X&\\ \hline \end{array} $$

The most similar rows (1 and 2, among others) share 2 markers and the solution is therefore optimal.

Answer 1

The following brutish algorithm does okay, it might be a start. It generates an optimal solution for $(10,8,3)$ and gets scores of 3 and 6 for $(10,30,9)$ and $(11,22,10)$, respectively by building the board one row at a time.

To create the first row, place markers in the first $r$ columns. To generate the next row, $R$, start with a row with no markers. While $R$ has less than $r$ markers:

• For each column $i$, create a candidate row $R_i$ which is $R$ but with a marker added to column $i$. (If $R$ already has a marker in column $i$, ignore this candidate).
• Score $R_i$ pairwise against each other row already added to the board, note the highest pairwise scoring as $S_i$.
• Among the rows already in the board, count how many also have a marker in column $i$, denote this count as $C_i$.
• Choose the column $c$ so that $S_c \le S_j$ for any $j \ne c$. If there are two columns with the same minimum score, choose the column with the lower $C_c$.
• Add a marker into column $c$.

Do this until all the rows have been generated.

For $(10,8,3)$ this generates the following table. Markers are numbered as they are added:

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&&&&&\\ \hline &&&1&2&3&&\\ \hline 3&&&&&&1&2\\ \hline &1&&2&&&3&\\ \hline &&1&&2&&&3\\ \hline 2&3&&&&1&&\\ \hline &&1&2&3&&&\\ \hline &&3&&&1&2&\\ \hline 3&2&&&&&&1\\ \hline &&&1&3&&&2\\ \hline \end{array}

A gist with a Python implementation can be found here: https://gist.github.com/maafy6/d414a7a561116f784063