Questions tagged [packing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
23
votes
5answers
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 ...
16
votes
1answer
756 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 ...
15
votes
1answer
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 ...
9
votes
1answer
679 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 ...
8
votes
1answer
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 ...
7
votes
1answer
412 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 ...
7
votes
0answers
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 ...
7
votes
0answers
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 ...
6
votes
2answers
576 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? ...
5
votes
1answer
167 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 ...
4
votes
2answers
3k 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 $\sum_{i\in{I}}{...
4
votes
3answers
486 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 ...
4
votes
1answer
141 views

Is set packing easier when the sets are squares?

I am interested in the following problem: ...
4
votes
0answers
146 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 ...
4
votes
0answers
102 views

Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem: ...
3
votes
1answer
62 views

Complexity of Finding Optimal Synergistic Set Packings

Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and ...
3
votes
0answers
199 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 ...
2
votes
1answer
154 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| ∈ ℕ, |B|...
2
votes
0answers
50 views

A “cut” packing problem

Consider the following maximisation problem. Given a path $P=\{1,2,\dots,n\}$ over $n$ vertices, a set $D\subseteq P\times P$ of "edges" and a set of positive integers capacities $\mathcal{C}=\{c_{i,...
2
votes
0answers
235 views

Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?

In the unweighted generalized assignment problem (UGAP) we have $n$ items and $k$ knapsacks. For each item $i$ and knapsack $j$, there is a weight $w_{ij}$. Also, every knapsack has a capacity $W$. ...
1
vote
2answers
2k 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$ ...
1
vote
1answer
289 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 ...
1
vote
1answer
242 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 ...
1
vote
1answer
218 views

Packing sets to maximize overlap

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$. Consider the following problem: Input: a list of $m$ weights $w = (w_1, \ldots, w_m)$, a list of $n$ distinct subsets $T = (S_1, \ldots, ...
1
vote
2answers
85 views

Partitioning a square for optimal queries

I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles: $f(x, y, r)$ tells me how many ...
1
vote
1answer
155 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 ...
1
vote
0answers
130 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 ...
1
vote
0answers
271 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 ...
0
votes
1answer
114 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 ...
0
votes
2answers
334 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 ...
0
votes
1answer
364 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 ...
0
votes
0answers
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 ...
0
votes
0answers
81 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 ...
0
votes
0answers
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 ...
-1
votes
2answers
123 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 ...