In an optimization setting the rearrangement algorithm can be seen as a method to compute (or at least approximate) the minimum maximal row sum (or maximum minimal row sum) of a matrix under independent perturbations of the entries in each column of a matrix. This problem is closely related to the multidimensional bottleneck assignment problem.
For matrices with only 2 columns the problem has an explicit solution (see [1] and the references therein). Dynamic programming yields a pseudopolynomial method if the number of rows is fixed, and using an integer programming reformulation the problem can be solved in polynomial time if the range of values in the matrix and the number of columns is fixed [2].
It has been shown in [3] that the problem is NP-hard, since classical makespan scheduling is a special case of it, and an approximation algorithm with multiplicative approximation guarantee (3/2 - (1/2)m) (where m denotes the number of rows) is presented there. This algorithm is not difficult to implement, but slower than the rearrangement algorithm.
In the classic OR setting, where the rows correspond to machines or workers, it is not natural to primarily look at asymptotic behavior for a growing number of rows. In the applications where each column arises from a quantization of some underlying continuous quantity this is different. Here the rearrangement algorithm seems to perform best.
In [2] it is shown that the rearrangement algorithm can terminate with an approximation error of Θ(N) for the very special class of matrices containing values 1,...,N in every column. This is contrary to the very good computational success in practice.
L. Rüschendorf. On the multidimensional assignment problem, Methods of Operations Research 47, 1983, pp 107-113. ISSN 0173-752X. (no DOI)
Utz-Uwe Haus. Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems. Operations Research Letters 43(1), 2015, pp 74–79.doi:10.1016/j.orl.2014.11.009
E. Coffmann and M. Yannakakis. Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum. Mathematics of Operations Research 9(3), 1984, pp 384 - 390.doi:10.1287/moor.9.3.384