Balancedness in the Weighted Rectangles Partitioning Problem

A rectangle is subdivided into pixels which are either active or inactive. The weighted rectangles partitioning problem (WRP) is finding a partition of the active pixels into weighted, smaller rectangles and maximizing the total weight. Using an IP formulation, instances with an integral relaxation polyhedron are characterized by the balancedness of the problem matrix. Is is discussed how this approach connects WRP to balanced hypergraphs. Numerical experiments illustrate the benefits of detecting balancedness for solving WRP.

Article

Download

View Balancedness in the Weighted Rectangles Partitioning Problem