On a 2-dimensional equipartition problem

The present paper deals with the following problem, which arises in a variety of applications: given a node-weighted rectangular grid graph, perform p horizontal full cuts and q vertical ones so as to make the weights of the resulting (p+1)(q+1) rectangular subgrids ‚as close as possible’. Computational complexity aspects are discussed. Several heuristic algorithms for obtaining partitions which minimize the maximum weight of a subgrid are developed, and computational results are reported. Theoretical bounds on the approximation error are also given.