Recently there was an article by Johannes Treitz submitted to Hacker News about how to display a set of pictures as nicely as possible. The article doesn’t have a formal description of the problem, so here is my take on what it mean by perfectly balanced.

The problem is not so well defined. To make sure the heights are close, do we minimize the sum of all differences? Minimize the maximum difference? Or maybe, we just want to minimize the difference between consecutive rows, such that the first row has height close to $h$.

Nevertheless, in real applications, the exact definition doesn’t matter that much. Treitz reduce the problem to the linear partition problem.

$a_i=W_i/H_i$ is the aspect ratio. This article will explore the techniques to solve the problem in $O(kn)$ time. It is only a high level overview, and leaves the details unfilled.

1 Minimize total difference

Let’s first consider a simpler problem for demonstration.

We will solve this problem with a reduction to a problem on a DAG, and then apply dynamic programming. Since we can always turn a problem that ask us to find the cost to a problem that ask us to find a construction that achieve the cost(with the same time/space bound). We will only concern with the cost version of the problem as it’s much clearer. (One can implement some arrows in Haskell to make DP for construction as easy as DP for cost, sounds like a nice project. )

Build a directed graph $D(V,A)$, where $V=\left\{v_1,\dots ,v_n\right\}$, $(v_i,v_j)\in A$ if and only if $i\le j$. (We can make it $i<j$ instead, depend on if we consider a empty sequence a valid sequence.)

We have a weight function $w(i,j)$ that assign weights to arc $(v_i,v_j)$. Define $w(i,j)=|{\sum }_{k=i}^{j-1}{a}_i-\mu |$.

If we find a $k$-edge path of minimum weight from $v_1$ to $v_n$, then this implies a solution to Problem 3.

2 Solve the minimum weight $k$-edge path problem

Define $C(d,i)$ to be the $d$-edge path from $v_1$ to $v_i$ with minimum weight. We want to find $C(k,n)$.

$$C(d,i)=\underset{1\le j\le i}{\min }C(d-1,j)+w(j,i)$$

If we set $w(j,i)=\infty$ if $j>i$, then we have a better representation.

$$C(d,i)=\underset{1\le j\le n}{\min }C(d-1,j)+w(j,i)$$

There are $kn$ entries in the DP table for $C$, and $C(d,i)$ requires $O(n)$ time to compute. This means the algorithm will take $O(k{n}^2)$ time.

3 Improve the time complexity

There is a standard technique on totally monotone matrices that can reduce the complexity of the problem to $O(kn)$.

^{Image Credit: Vanessa Li.}

Define a matrix $M^d$, such that $M_{j,i}^d=C(d-1,j)+w(j,i)$, the original recurrence become $$C(d,i)=\underset{1\le j\le n}{\min }{M}_{j,i}^d$$ In other words, $C(d,i)$ is the $i$th column’s minima of $M^d$.

Using the SMAWK algorithm, all column minimas can be found in $O(n)$. Finding $C(d,i)$ takes only $O(1)$ time on average!

Here is the very simple code to show how this can be done easily if we have a Haskell implementation of the SMAWK algorithm. The indexing is a bit different from the description in the article.

import Data.Array
import SMAWK

minCostkEdgePath k n w = d!(k-1,n)
  where
    d = array ((0,0),(k-1,n)) [ ((i,j), f i j) | i<-[0..k-1],j<-[0..n]]
    f 0 i = w 0 i
    f k i = m k (p!(k,i)) i
    p = array ((1,0),(k,n)) [((z,i),t) |z<-[1..k],(i,t)<-zip [0..n] (columnMinima (m z) (n+1) (n+1))]
    m k j i = (+) (d!(k-1,j)) (w j i)

minCostMuPartition k xs = minCostkEdgePath k n w
    where 
        w i j 
         | i <= j    = abs $! s!j - s!i - avg
         | otherwise = 2*m
        s   = listArray (0, n-1) $ scanl (+) 0 xs
        n   = length xs
        m   = sum xs
        avg = m/fromIntegral k

4 Solve the linear partition problem

Now, returning to the original problem. Again, we can reduce the problem to a problem on a directed graph. This time, $w(i,j)={\sum }_{k=i}^{j-1}{a}_i$. The weight of a path is the maximum weight of the edges in the path. A $k$-edge path with minimum weight implies the solution to the original problem.

$$C(d,i)=\underset{1\le j\le n}{\min }{M}_{j,i}^d$$

where $M_{j,i}^d=\max (C(d-1,j),w(j,i))$.

Just like Problem 3, this describes a $O(k{n}^2)$ time algorithm. Compare $w,C$ and $M^d$ with the previous problem to see there isn’t much difference.

5 Improve the time complexity, again

Can we define an alternative to the Monge property? Yes, we can extend this to algebraic Monge property. Just replace $+$ with some associative operation $\oplus$, $\le$ with a total order that is ordered with respect to $\oplus$, i.e. $a\le a\oplus b$.

So it seems, using the algorithm above with little modification, we can solve the problem in $O(kn)$ time because we can just replace $+$ by $\min$.

However, algebraic Monge property in general doesn’t imply totally monotone matrix.

Consider the simple matrix, and our operation is $\max$.

$\max (1,2)=\max (0,2)$, but the matrix is not totally monotone. $1>0$ but $2\ngtr 2$.

If instead the operation is strictly compatible, i.e. $a\oplus b<a\oplus c$ if $b<c$, then we can always produce a totally monotone matrix. This is not the case with $\max$.

Some readers who are familiar with $L^p$ space might point out for any sequence of reals $a_1,\dots ,a_n$ and $ϵ>0$, there exist a $p\ge 1$, such that $({\sum }_{i=1}^n|a_i{|}^p{)}^{1/p}-{\max }_{i=1}^n|a_i|<ϵ$. So if we don’t need to be exact, pick a large enough $p$ as an exponential is good enough. This opens up a can of numerical analysis.

A more restrictive but good enough variant of the Monge property hold.

Our $w$ in consideration has strict bottleneck Monge property. Because all the numbers are positive, $w(i,j+1)>w(i+1,j+1)>w(i+1,j)$, $w(i,j+1)>w(i,j)>w(i+1,j)$. A simple case check on the relation between $w(i,j)$ and $w(i+1,j+1)$ will give the desired proof. Why this property? You can check by a case by case proof that this property implies total monotonicity.

There seems to be a direct proof by analyze 12 different cases, but I got too bored after the second case. One can read [1] for the proof. It doesn’t contain the exact theorem, but a result that implies this one. The proof is quite involved. Their idea is to construct a new matrix with a new operation over sorted sequences of numbers instead of just numbers. Prove this matrix is strictly compatible and has the algebraic Monge property, and show this can always be done if the original matrix has the strict bottleneck Monge property.

The final punchline.

6 Rethink the original problem

We have developed a $O(kn)$ algorithm for Problem 2. As we can see from the practical application, this is a $O(n^2)$ algorithm because the $k$ is of the order $n$.

For a few hundred photos, we can afford to run it in real time. This will reach a limit once there are thousand of photos.

Can we do better? Yes, by considering a different kind of reduction(thank god we didn’t formally define what close means). Instead of compute $k$ and try to fit $k$ rows, why not just make sure each row’s width is almost the width we want and scale accordingly? We want each rows to approximately have width $W$, we don’t really care how many rows there are.

This is the exact same problem described on section 5 of [1]. It can be solve in $O(n)$ time.

7 Update

We did some more investigation into this problem.

References