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