PARTITIONING A MATRIX TO MINIMIZE THE MAXIMUM COST

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