Recognizing Integrality of Weighted Rectangles Partitions

The weighted rectangles partitioning (WRP) problem is defined on a set of active and inactive pixels. The problem is to find a partition of the active pixels into weighted rectangles, such that the sum of their weights is maximal. The problem is formulated as an integer programming problem and instances with an integral relaxation polyhedron are characterized by the balancedness of the problem matrix.Numerical experiments illustrate the benefits of detecting balancedness for solving WRP.

Article

Download

View Recognizing Integrality of Weighted Rectangles Partitions