Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [packing]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
123 views

### Re-packing of integers into fixed-size bins

We are given a constant $B$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$, and 2) a packing of these numbers into $N/B$ bins of size $B$. An adversary ...
49 views

325 views

### Packing $n$ objects into $m$ bins whose size is variable

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
118 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 ...
145 views

### What is the current “state-of-the-art” solver for quadratic knapsack problems?

New to this forum, so please let me know if my question format is incorrect. For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have ...
129 views

### 3D Bin Packing with one bin with infinite/unknown size

Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size. I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$. The dimensions of the items are ...
235 views

### Scheduling to maximize idle time

In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due ...
358 views

### Hardness of an extended maximum set packing problem

(Edited) The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$. The requirement in this problem is that the sets in the solution will be ...
198 views

### Variation of bin packing

My problem is related to the standard bin packing problem, but in my case each item has a value, and the objective is to minimise the number of bins used to pack all the items PLUS the sum of the ...
113 views

### Packing problems with repetitions

In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the ...
102 views

### Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem: ...
270 views

### Bin packing upper bound: total size of items = k, bin size = r

Suppose you have items, whose total size (i.e. sum of sizes) is $k$. The number of items and their individual sizes are unknown integers. We need to pack the items into bins of size $r$. I need to ...
141 views

### Is set packing easier when the sets are squares?

I am interested in the following problem: ...
549 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 ...
193 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 ...
154 views

613 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 ...
410 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 ...
121 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 ...
575 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? ...
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 ...