tailieunhanh - Báo cáo toán hoc:" A dual of the rectangle-segmentation problem for binary matrices "

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A dual of the rectangle-segmentation problem for binary matrices. | A dual of the rectangle-segmentation problem for binary matrices Thomas Kalinowski Institut fur Mathematik Universitat Rostock 18051 Rostock Germany Submitted Apr 23 2009 Accepted Jul 11 2009 Published Jul 24 2009 Mathematics Subject Classification 90C27 90C46 Abstract We consider the problem to decompose a binary matrix into a small number of binary matrices whose 1-entries form a rectangle. We show that the linear relaxation of this problem has an optimal integral solution corresponding to a well known geometric result on the decomposition of rectilinear polygons. 1 Introduction In the context of intensity modulated radiation therapy several decomposition problems for nonnegative integer matrices have been considered. One of these is the decomposition into a small number of binary matrices whose 1-entries form a rectangle. There is an example showing that in general the linear relaxation of this problem has no optimal integral solution 1 . On the other hand the same paper contains an algorithm based on the revised simplex method that uses only very few Gomory cuts. In computational experiments this algorithm provided exact solutions for matrices of reasonable size in short time. In the present paper we consider the special case that the input matrix is already binary A G 0 1 mxra. In this case the integer optimization problem is equivalent to a well studied geometric problem the decomposition of a rectilinear polygon into the minimal number of rectangles. Our main result is that the minimal number of rectangles in such a decomposition equals the optimal objective in the relaxed matrix decomposition problem. In other words the integrality gap vanishes provided the input matrix is binary. This solves problem 1 of 1 . 2 Notation and problem formulation Let A be a binary matrix of size m X n. A rectangle matrix is an m X n matrix S sij such that for some integers k1 k2 11 and l2 with 1 k1 k2 m and 1 11 l2 n THE ELECTRONIC JOURNAL OF .