For planning rearrangements of objects in a clutter, it is required to know the goal configuration of the objects. However, in real life scenarios, this information is not available most of the time. We introduce a novel method that computes a collision-free placement of objects on a cluttered surface, while minimizing the total number and amount of displacements of the existing moveable objects. Our method applies nested local searches that perform multi-objective optimizations guided by heuristics. Experimental evaluations demonstrate high computational efficiency and success rate of our method, as well as good quality of solutions.
Related work in other areas A closely related problem to object placement, studied in computer graphics and operations research, is the packing problem (also known as the knapsack problem), where the goal is to place as many objects as possible in a non-overlapping configuration within a given empty container. The packing problem is NP-hard @cite_0 . It has been widely studied in 2D (cf. the survey @cite_14 ). It has been also studied in 3D under various conditions restrictions @cite_26 @cite_9 @cite_15 (e.g., packing a set of polyhedrons into a fixed size polyhedron without considering rotations @cite_2 , orthogonal packing of tetris-like items into rectangular bins @cite_12 @cite_20 ).
@cite_14 @cite_26 @cite_9 @cite_0 @cite_2 @cite_15 @cite_20 @cite_12
2770216739 1530649098 2000444555 2962797157
We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. In this paper, we break the 2 approximation barrier, achieving a polynomial-time (17 9 + ) < 1.89 approximation, which improves to (558 325 + ) < 1.72 in the cardinality case. Essentially all prior work on 2DK approximation packs items inside a constant number of rectangular containers, where items inside each container are packed using a simple greedy strategy. We deviate for the first time from this setting: we show that there exists a large profit solution where items are packed inside a constant number of containers plus one L-shaped region at the boundary of the knapsack which contains items that are high and narrow and items that are wide and thin. As a second major and the main algorithmic contribution of this paper, we present a PTAS for this case. We believe that this will turn out to be useful in future work in geometric packing problems. We also consider the variant of the problem with rotations (2DKR), where items can be rotated by 90 degrees. Also, in this case, the best-known polynomial-time approximation factor (even for the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time (3 2 + )-approximation for 2DKR, which improves to (4 3 + ) in the cardinality case. We consider the two-dimensional geometric knapsack problem defined as follows. Given a collection of rectangular axis-parallel items with weights, we want to find a maximum weight subset of the items that can be packed into a rectangular knapsack, i.e., which can be assigned positions within the knapsack such that the items are pairwise non-overlapping. The goal is to compute the optimal collection of items together with a feasible packing. The problem arises naturally in several applications, and various special cases of the problem have been studied. For the general case the best known result is a (2 + e)-approximation algorithm, while the only hardness result is NP-hardness. Our main result is a (1 + e)-approximation algorithm that runs in quasi-polynomial time, provided that the input data consists of (quasi-)polynomially bounded integers. We achieve this result in the setting with and without allowing rotation of the items. Our key technical contribution is to show the existence of a partition for the knapsack into a small number of rectangular boxes. Intuitively, this partition describes the segmentation of the knapsack in some near-optimal solution into large items, areas containing items that are high and thin, and areas containing items that are small and wide. Handling the interaction between these three types of items is a core bottleneck in the design of approximation algorithms for the problem and our partition allows to control this at only marginal cost. In particular, it is so powerful that we do not even need to round the sizes of the items, which is a canonical step in algorithms for geometric knapsack, geometric bin-packing, etc. Finally, we present new algorithms for two-dimensional knapsack and two-dimensional bin-packing under (1 + e)-resource augmentation with a substantially better running time dependence on e (although at the expense of requiring quasi-polynomial time). The objective value of our computed solutions is as good as the optimum without additional resources. Here we exploit a recent result showing the existence of certain low-complexity low weight separators for sets of non-overlapping rectangles. The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of @math items and @math bins (knapsacks) such that each item @math has a profit @math and a size @math , and each bin @math has a capacity @math . The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461-474], and thus far, this was also the best known approximation for MKP @. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP @. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with @math distinct sizes and profits. We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+&#x03B5; [Jansen and Zhang, SODA 2004]. In this paper we break the 2 approximation barrier, achieving a polynomialtime 17 9 + &#x03B5;