Partitioning a matrix to minimize the maximum cost Original Research Article

A matrix A = [aij] of nonnegative integers must be partitioned into p blocks (submatrices) corresponding to a set of vertical cuts parallel to the columns and a set of horizontal cuts parallel to the rows. With each block is associated a cost equal to the sum of its elements. We consider the problem of finding a matrix partitioning that minimizes the cost of the block of maximum cost. In this paper a mathematical formulation of the problem is given and used to derive both exact and heuristic algorithms. Lower bounds and dominance criteria are exploited in a tree search algorithm for finding the optimal solution of the problem. Computational results of the proposed algorithm are given on a number of randomly generated test problems.