Partitioning a matrix with non-guillotine cuts to minimize the maximum cost. (English) Zbl 0993.68001

Summary: We consider the problem of partitioning a matrix of \(m\) rows and \(n\) columns of nonnegative integers into \(M\) smaller submatrices. With each submatrix is associated a cost equal to the sum of its elements. The objective is to minimize the cost of the submatrix of maximum cost. We present a (0-1)-integer programming formulation of the problem and three different lower bounds. A heuristic procedure for finding a valid upper bound to the optimal solution cost is also described. Problem reduction tests derived from both the original problem and the lower bounds are given. Lower bounds and reduction tests are used in a tree search algorithm in order to find the optimal solution to the problem. Computational results on a number of randomly generated test problems are presented.


68M07 Mathematical problems of computer architecture
90C47 Minimax problems in mathematical programming


Full Text: DOI


[1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows, (1993), Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Beasley, J.E., An exact two-dimensional non guillotine cutting tree search procedure, Oper. res., 33, 49-63, (1985) · Zbl 0569.90038
[3] Becker, R.I.; Lari, I.; Lucertini, M.; Simeone, B., Max – min partitioning of grid graphs into connected components, Networks, 32, 115-125, (1998) · Zbl 0990.05117
[4] Fisher, M.L., The Lagrangean relaxation method for solving integer programming problems, Management sci., 27, 1-18, (1981) · Zbl 0466.90054
[5] Green, S., Parallel processing for computer graphics, (1991), Pitman London
[6] De Keyser, J.; Roose, D., Load balancing data parallel programs on distributed memory computers, Parallel comput., 19, 1199-1219, (1993)
[7] A. Mingozzi, S. Morigi, Min – max partitioning of a matrix with non-guillotine cuts, Technical Report, Department of Math., University of Bologna, 1996. · Zbl 0993.68001
[8] Mingozzi, A.; Ricciardelli, S.; Spadoni, M., Partitioning a matrix to minimize the maximum cost, Discrete appl. math., 62, 221-248, (1995) · Zbl 0833.90086
[9] Priol, T.; Bouatouch, K., Static load balancing for a parallel ray tracing on a MIMD hypercube, Visual comput., 5, 109-119, (1989)
[10] Shivaratri, N.G.; Krueger, P.; Singhal, M., Load distributing for locally distributed systems, IEEE comput., 25, 33-44, (1992)
[11] Williams, R.D., Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: practice experience, 3, 456-481, (1991)
[12] Yuan, X.; Salisbury, C.; Balsara, D.; Melhem, R., A load balancing package on distributed memory systems and its application to particle – particle, particle – particle mesh methods, Parallel comput., 23, 1525-1544, (1997) · Zbl 0894.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.