## Approximations for the general block distribution of a matrix

Bengt Aspvall
Department of Computer Science, University of Bergen, Bergen, Norway.

We analyze the performance guarantee of a natural and practical heuristic based on iterative refinement, which has previously been shown to give good empirical results. When $p^2$ is the number of blocks, we show that the tight performance ratio is $\theta(\sqrt{p})$. When the matrix has rows of large cost, the details of the objective function of the algorithm are shown to be important, since a naive implementation can lead to a $\Omega(p)$ performance ratio. Extensions to more general cost functions, higher-dimensional arrays, and randomized initial configurations are also considered.
In comparison, Khanna et al.\ have shown the problem to be approximable within $O(1)$ factor \cite{KMS97}, while Grigni and Manne have shown it to be NP-hard to approximate within any constant factor less than two \cite{GM96}.