The packing tag has no wiki summary.
7
votes
1answer
134 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 ...
4
votes
0answers
103 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 ...
2
votes
1answer
105 views
How can I reduce this kind of BinPack algorithm? (“MinBreak-BinFill”)
I have a special variant of BinPack problem.
Does anyone know how to reduce this problem to something known?
The problem:
There are items $I$ and bins $B$ in specific quantity and size.
$|I| ∈ ℕ, ...
13
votes
1answer
182 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 ...
0
votes
0answers
68 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 ...
9
votes
1answer
733 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 ...
0
votes
2answers
264 views
Bin packing approximation with different bin sizes
Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?
More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ ...
3
votes
3answers
212 views
bin packing with overlapping objects
I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object ...
1
vote
1answer
109 views
Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area
I'm trying to find a solution for the following problem.
You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and ...
3
votes
1answer
302 views
For efficient algorithm on “minimization” knapsack problem
Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B>0$. How to pick a set of indexes $I$, so that
$\sum_{i\in{I}}{b[i]}\geq{B}$
To minimize ...
5
votes
0answers
231 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 ...
7
votes
1answer
243 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 ...
0
votes
0answers
102 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 ...
6
votes
2answers
252 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?
...
20
votes
5answers
813 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 ...
6
votes
1answer
308 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 ...
