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$ 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$ 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$ 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$ 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

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.