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?

  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Jan 23 '19 at 14:25
  • $\begingroup$ @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 :) $\endgroup$ – orlp Jan 23 '19 at 14:28
  • $\begingroup$ 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). $\endgroup$ – j_random_hacker Jan 23 '19 at 14:45
  • $\begingroup$ @j_random_hacker I expect the tables to be roughly 256 x c, with c being anywhere from ~15 up to 1000. $\endgroup$ – orlp Jan 23 '19 at 14:57
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Jan 23 '19 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.