Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Input:

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

share|improve this question
    
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. –  hardmath Nov 29 '12 at 14:37
    
Are you searching for the best matrix only? Will good approximation (not best) be enough? –  Egor Skriptunoff Nov 29 '12 at 14:44
    
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). –  joriki Nov 29 '12 at 14:55
    
Of course, I mean row of the matrix not line. I'm only interested in the max value of the optimal matrix described above. –  EQ1 Nov 29 '12 at 15:11
    
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? –  Egor Skriptunoff Nov 29 '12 at 15:13

1 Answer 1

up vote 2 down vote accepted

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

dist = -1
repeat
  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
    end-if
  end-for
until success
print(dist)
share|improve this answer
    
+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. –  hardmath Nov 29 '12 at 20:49
    
@hardmath - I think my algorithm is correct. (Do you have counterexample?) It relies on left justified filling to properly handle possible overlapping. –  Egor Skriptunoff Nov 29 '12 at 22:40
    
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. –  Egor Skriptunoff Nov 29 '12 at 23:13
    
That's the right idea, I have no doubt. I'm posting from my cellphone and will give an example when I get home. –  hardmath Nov 29 '12 at 23:31
    
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. –  hardmath Nov 30 '12 at 1:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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