This optimization question popped into my mind while working with latex tables:
Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ which is a paragraph of words to be put in the cell $(i,j)$. We also know that the table is going to span the whole text width of a page, which is $w$ characters. The question is:
How to find the optimal combination for width of columns, so that the height of the table is minimized?
I appreciate any thoughts on the complexity of the problem or an algorithm to solve it efficiently.
The only reasonable solution that comes to mind is a DP algorithm that iterates through the allowed width of the page.
Each iteration you try to extend the allowed page width from k to k+1. To do this, you select a particular entry (i,j), and extend its width by 1, and then update the height of this particular row i by taking the max over all the heights of the entries in this row. Then, you take the minimum over all the entries that you tried to update. This will give the minimum height of the current row using an overall page width of k+1.
You also need to update the width of every entry in column j in order to make sure the table lines up.
I think the overall running time will be something like $O(w m n^2)$.
Note that I don't think you'll be able to find an efficient solution. This problem reminds me of the knapsack problem, which is NP-Complete. I don't have a reduction right now, but I will think about it later.