6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Player one will place a fixed number $r$ of markers such that the two rows." - is there supposed to be more here? It sounds like player one is placing $r$ markers in each row, is that correct? $\endgroup$ – DylanSp Feb 3 '16 at 13:51
  • $\begingroup$ @DylanSp You're right! I must have changed my mind when phrasing the question. Thanks for pointing that out. $\endgroup$ – Block Feb 3 '16 at 13:56
  • $\begingroup$ Can you check your example instances? If m=10 and n=30, how can r be 90? 90 markers in each row, but there's only space for 30 markers. I feel like the order of those numbers should be changed. $\endgroup$ – Duncan Feb 3 '16 at 17:55
  • 1
    $\begingroup$ Do you have solutions for your lower bound examples? I'm playing around with it, but can't figure out how to get anywhere close to those numbers. $\endgroup$ – Matt Feb 4 '16 at 14:26
  • 1
    $\begingroup$ @Matt I have added an example of an optimal solution. $\endgroup$ – Block Feb 4 '16 at 15:45
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I have Python code that I'm using to test this out. Not sure what the etiquette on posting that in the answer is. $\endgroup$ – Matt Feb 4 '16 at 16:37
  • 1
    $\begingroup$ Looks promising! I am going to take a proper look during the week end. Thanks! $\endgroup$ – Block Feb 5 '16 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.