1
$\begingroup$

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

  • 0
    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.2012-11-29
  • 0
    Are you searching for the best matrix only? Will good approximation (not best) be enough?2012-11-29
  • 0
    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).2012-11-29
  • 0
    Of course, I mean row of the matrix not line. I'm only interested in the max value of the optimal matrix described above.2012-11-29
  • 0
    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?2012-11-29
  • 0
    I agree on the brute force complexity. Though, since I only need that max value that this optimal matrix will have isn't there a better way?2012-11-29
  • 0
    For searching only value of optimal distance brute-force time complexity would be O((max distance from $j_k$ to 1)*n).2012-11-29
  • 0
    That would be excellent. Can you be more precise and describe the algorithm?2012-11-29

1 Answers 1

2

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) 
  • 0
    +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.2012-11-29
  • 0
    @hardmath - I think my algorithm is correct. (Do you have counterexample?) It relies on left justified filling to properly handle possible overlapping.2012-11-29
  • 0
    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.2012-11-29
  • 0
    That's the right idea, I have no doubt. I'm posting from my cellphone and will give an example when I get home.2012-11-29
  • 0
    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.2012-11-30
  • 0
    @hardmath - I supposed that matrix columns may be added in both directions, it seems me to be more naturally for problems arised from real life. In case of positive-only column indexes I fully agree with you.2012-11-30
  • 0
    Columns may be added in both directions. That is if $j_1=3$ and $b_1=9$ you're allowed to place 4 columns on the left of $j_1$ and 4 columns on the right. You've been all very helpful. Thank you and especially thank you Egor Skriptunoff .2012-11-30