We investigate how to partition a rectangular region of length @math and height @math into @math rectangles of given areas @math using two-stage guillotine cuts, so as to minimize either (i) the sum of the perimeters, (ii) the largest perimeter, or (iii) the maximum aspect ratio of the rectangles. These problems play an important role in the ongoing Vietnamese land-allocation reform, as well as in the optimization of matrix multiplication algorithms. We show that the first problem can be solved to optimality in @math , while the two others are NP-hard. We propose mixed integer programming (MIP) formulations and a binary search-based approach for solving the NP-hard problems. Experimental analyses are conducted to compare the solution approaches in terms of computational efficiency and solution quality, for different objectives.
Partitioning an area into polygons of fixed shape or area is a class of problems which has been regularly studied in the operations research and computational geometry literature. @cite_5 @cite_6 defined two optimization problems that seek to partition the unit square into a number of rectangles with given areas, so as to optimize parallel matrix-multiplication algorithms in heterogeneous parallel computing platforms. The first problem aims to minimize the sum of all rectangle perimeters, whereas the second problem aims to minimize the largest perimeter. These problems are special cases of and where the general rectangular region is a square. The authors introduced an @math -approximate algorithm and an @math -approximate algorithm for these problems, respectively.
@cite_5 @cite_6
1494149077 2022366735
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s 1 , s 2 , . . . ,s p (such that Σ i=1 p s i = 1 ), so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7 4 -approximation algorithm for (i) and a @math -approximation algorithm for (ii). Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.