The constraints are…
Each rectilinear block must be placed
Minimize the area (x*y)
Create a ring such as below
Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples.
I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable?
Are you stating all of the constraints? To minimize the x*y area, it would often be preferable to have two very long sides and two very short ones for the inner rectangle.
For example, say that all rectangles are the same shape and that there are 4n of them. They could be arranged to leave a square in the middle. Let's say the size of the square is a*a and that the four outer areas are also a*a. The x*y area would then be 3a*3a=9a^2.
But instead of leaving an inner square, we can reduce two of its sides by 50% and increase the other two by 50%. Now we have an area of (7a/2)(5a/2) = (35/4)a^2, which is slightly smaller. The size of the inner rectangle is now (a/2)*(3a/2) = (3/4)a^2 instead of a^2.
If the problem can be stated more clearly, my guess is that it's a variant of the bin packing problem[^]. The article mentions that this problem is NP-hard, which effectively means that the time required to find the optimal solution rises exponentially, although it may be possible to more efficiently find a solution that is known to bounded in terms of how close it is to the optimal one.
Given an array A of n integers and k <= n, we want to choose k numbers from this array and split them to pairs, such that the sum of the differences of those pairs (in absolute value) is minimal.
Does someone have an idea? Where do I start from in this problem?