# Computing (near) optimal displacement tables

Suppose we have a two-dimensional table $$T$$ with $$r$$ rows and $$c$$ columns that is sparse. Let $$T[i][j]$$ be the element at the $$i$$th row and $$j$$th column of $$T$$, with zero-based indexing.

We can compress $$T[i][j]$$ by putting all elements in a single 1D array $$A$$, and letting $$A[D[i] + j] = T[i][j]$$. Now with $$D[i] = ci$$ we have simply flattened the table.

But if the table is (very) sparse, we can do better than $$D[i] = ri$$. We can overlap rows where they're sparse! As an example we could have the table:

$$\begin{bmatrix} 0 &1 & 0 & 0 & 0\\ 2 & 6 &0 & 0 &0\\ 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 4 & 0 & 9\\ 0 & 0 & 0 & 0 & 5\\ \end{bmatrix}$$

Which we could compress like such:

$$A = [2, 6, 4, 3, 9, 1, 5]$$ $$D = [4,0,0,0,1]$$

Finally, to detect non-existing entries we also need a table of the same size as $$A$$ that tracks the source row of each entry:

$$C = [1, 1, 3, 2, 3, 0, 4]$$

Only when $$C[D[i] + j] = i$$ we consider $$A[D[i] + j] = T[i][j]$$, otherwise we deduce $$T[i][j] = 0$$. We also assume that when $$D[i] + j \geq |A|$$ that the element is zero.

Now the question is, what is a (near) optimal choice of $$D$$? We need to shift each row of $$T$$ so that each column only contains at most one non-zero element. A fast greedy method would be to handle each row in descending order of number of elements, and assign $$D$$ for that row in the first spot that doesn't cause a conflict.

But that isn't optimal. Is there another reasonably fast algorithm that provides better or optimal results?

• Very interesting problem! Consider the special case in which $c=2r+k$ and each row begins with a 1 followed by $r-1$ zeros, and ends with $r-1$ zeros followed by a 1, with $k$ "meat" entries in the middle, and the goal is to see whether we can fit all of the rows into an $A$ of size $3r+k-1$: I think this retains the essential "hardness" of the problem, and from this perspective the problem becomes one of ordering the rows (since each row must then have a unique offset in the range $[0, r-1]$) -- but I can't think of a reduction from Hamiltonian Path. – j_random_hacker Jan 23 '19 at 14:25
• @j_random_hacker While a reduction would be interesting in it's own right, I wouldn't be surprised if it's NP complete whatsoever, and already am surrendering myself to approximations :) – orlp Jan 23 '19 at 14:28
• Ah :) If $c$ is small, say, < 30, then you could fix a tentative size $s$ for $A$, do dynamic programming on subsets of column positions in $O(2^ssr)$ time, all this inside a binary search on $s$ to find the minimal size with a solution (this adds another $\log c$ factor). – j_random_hacker Jan 23 '19 at 14:45
• @j_random_hacker I expect the tables to be roughly 256 x c, with c being anywhere from ~15 up to 1000. – orlp Jan 23 '19 at 14:57
• I would probably go with beam search on the non-tiny instances for this -- basically, a version of branch and bound that lets you trade off solution quality for time. Rather than picking as the row to place next the one that has the most nonzeros, I think you would do better by placing the one whose best placement increases the width of the current partial solution by the most, but I could easily be wrong about that. – j_random_hacker Jan 23 '19 at 15:11