I'm searching for an algorithm that efficiently does the following


  • $n\in \mathbb{N}$
  • $j_1,j_2,\ldots ,j_n$ with the property $j_1<j_2<\cdots<j_n$
  • $b_1,\ldots ,b_n \in \mathbb{N}$
  • $m\geq b_1+\cdots+b_n$

Output: a Matrix of $n\times m$ with the property described bellow:
To be more precise, I have a special case of an $n\times m$ matrix ($n$ is given, $m$ has a bounded lower value equal to $b_1+b_2+\cdots+b_n$ but we can choose it to be arbitrary large if we like).

We are also given a series of coordinates $j_1<\cdots<j_n$ that each defines a position in line 1,2 etc. For example if $j_1=3$ then the postion $(1,3)$ of the matrix. Matrix elements are 0 or 1 under the constrain that each column can have at most one 1 and each line $i$ exactly $b_i$ 1s.

From all the possible matrices we're interested in finding one ( one certainly exists) that has the the following property:

$\max\{|j_k-\mathrm{positionOf}(1)|, k= 1,\ldots,n$ and for all 1 appearing on each of the $i_k$ line$\}$ is the lowest of all the other possible matrices. Less formal, I want to find one of the matrices that minimizes the biggest distance of '1' from $j_k$ for all $j_k$.

Is there an algorithm (preferably of linear complexity) to find such an array? My best effort so far solves it in polynomial time but it's really a brute force solution and not very applicable.

Thank you in advance.

  • $\begingroup$ Your write-up is not clear enough. By $i_k$ "line" are you talking about the kth row of your matrix? You name a lot of the elements of your problem but neglect to give a symbol for the matrix itself. This is an optimization problem, if I understand it, so asking for a linear time search for the optimal matrix seems to be ambitious. $\endgroup$ – hardmath Nov 29 '12 at 14:37
  • $\begingroup$ Are you searching for the best matrix only? Will good approximation (not best) be enough? $\endgroup$ – Egor Skriptunoff Nov 29 '12 at 14:44
  • $\begingroup$ The things perpendicular to the columns are usually called rows, not lines. (It's the same word for both in German.) I agree that "$k$-th row" instead of "$i_k$ line" would make more sense; everything else seems clear enough to me (if sometimes somewhat unorthodox). $\endgroup$ – joriki Nov 29 '12 at 14:55
  • $\begingroup$ Of course, I mean row of the matrix not line. I'm only interested in the max value of the optimal matrix described above. $\endgroup$ – EQ1 Nov 29 '12 at 15:11
  • $\begingroup$ As for searching for the best matrix, brute-force time complexity is not greater than O((max distance from $j_k$ to 1)*(sum of all $b_k$)). Is it not enough? $\endgroup$ – Egor Skriptunoff Nov 29 '12 at 15:13

Algorithm for searching the best value of max distance from $j_k$ to 1

dist = -1
  dist = dist + 1
  pos = -infinity
  success = true
  for k = 1 to n 
    pos = max(pos, j[k] - dist)
    pos = pos + b[k]
    if pos > j[k] + dist + 1 then
      success = false
      terminate the execution of "for" loop
until success
  • $\begingroup$ +1 for getting the complexity bounded, but I don't think your loop properly accounts for the possibility that intervals [j[k]-dist,j[k]+dist] may overlap. $\endgroup$ – hardmath Nov 29 '12 at 20:49
  • $\begingroup$ @hardmath - I think my algorithm is correct. (Do you have counterexample?) It relies on left justified filling to properly handle possible overlapping. $\endgroup$ – Egor Skriptunoff Nov 29 '12 at 22:40
  • $\begingroup$ It is easy to prove this statement: If matrix exists for some "dist" value, then it can be transformed to left-justified form preserving it's "dist" value, so that matrix looks like a ladder, i.e., all "1" on k-th row located to the left of all "1" on (k+1)-th row. Thus, only left-justified matrices should be brute-forced. This is the idea of the algorithm. $\endgroup$ – Egor Skriptunoff Nov 29 '12 at 23:13
  • $\begingroup$ That's the right idea, I have no doubt. I'm posting from my cellphone and will give an example when I get home. $\endgroup$ – hardmath Nov 29 '12 at 23:31
  • $\begingroup$ Let's assume (the OP doesn't specifically say) that the j[k] are positive integers (though the example given is, j[1]=3); also the column indexes are necessarily positive integers. I guess my change comes down to initializing pos=1 rather than -infinity. Given dist, then the first available position in row 1 is pos = max(pos,j[1]-dist). After left-filling b[1] ones, the next "empty" position is in pos+b[1], and I agree with how you test for failure (and update pos), and the for-loop continues. $\endgroup$ – hardmath Nov 30 '12 at 1:03

Your Answer

