# Questions tagged [packing]

The tag has no usage guidance.

38 questions
Filter by
Sorted by
Tagged with
2k views

### Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
918 views

### What is the complexity of rectangle packing when rotations are allowed?

In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$. The task is to find a placement of $r_1,\ldots,r_n$ inside $R$ such that none of ...
1k views

### Is the following problem NP hard?

Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer. The goal is to find ...
715 views

### Fitting minimum number of rectangles of width/height 1 into a 2D grid

Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
779 views

### NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
433 views

### Does this bin packing problem have a name?

My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
197 views

### What is the complexity of pallet loading for identical non-rectangular objects?

In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the ...
664 views

### Hardness of Approximation results for Special Set Packing Problem Wanted

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem? The general Set Packing Problem would be: Given A Collection of ...
662 views

### Bin Packing with uniform size constraints

Consider the following version of the Bin Packing problem: We are given $k$ unit-size bins and $n$ items with sizes $\epsilon < a_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins? ...
179 views

### Does the following type of hitting problem have a name?

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
3k views

52 views

162 views

### Is pooling-aware bin packing NP-Hard?

I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ...
123 views

### Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
82 views

### Partitioning based on distribution

Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. For two bins and uniform distribution, this problem is ...
123 views

### On algorithms that minimizes maximal load of bins

There are $n$ bins and $m$ balls, $b_i$ where $0<i\le m$. Balls are with different weights $w_i$ and have dependency between them. ball $b_1$ depends on $b_2$, $b_2$ depends on $b_3$, and so on. It ...
146 views

### How to continue this algorithm? [closed]

I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º). I have thought about ...