# Questions tagged [packing]

Packing problems are a class of optimization problems in which one has to pack objects together as densely as possible. One could be for example packing rectangles inside a rectangle.

72 questions
Filter by
Sorted by
Tagged with
2k views

### How to pack polygons inside another polygon?

I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls. I can scan the leather sheets ...
2k views

### How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the ...
251 views

### guillotine cuts versus general cuts

Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and ...
384 views

39 views

### How to show that there are $\binom{M+K}{M}$ different number of type bins?

In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma. Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the ...
564 views

### Packing chocolate boxes

I've been trying to solve an interesting problem created by one of my friends. The following is the problem statement: There are $n$ types of chocolates. $\langle a_1,a_2,a_3....a_n \rangle$ are ...
369 views

### Bin-packing satisfiability rather than minimization

Here's a problem I need to solve that's clearly related to the standard bin-packing problem, but I'm not sure how to approach it. Suppose you have some finite set of bins $B$, and each $b_i \in B$ ...
18 views

### Optimal distribution of N points in non euclidean volume, where each point is furthest away from the others

Given N points, I want to find the optimal configuration for which all the points are as far away from each other as possible. The metric I'm considering is an approximation to the perceived distance ...
25 views

### Optimize stacking time series by offsetting start times (feels like a backpack problem?)

Given a time-series of data collected from a single running process that takes 8 hours to complete: Minute GB of Disk Space Used 0 0 1 8 2 15 3 22 ...Etc. It is sampled every minute, for 8 ...
290 views

Is this problem a know variant of the optimisation version of the bin packing problem? There is an approximating algorithm for it? Let $A = \{a_1,a_2,...a_n\}$ be a set of items, $B = \{b_1,b_2,...... 1answer 279 views ### Set packing variant There are n collections of M sets. Pick a single set from each collection, such that all n picked sets are pairwise disjoint. This problem can be converted to the ... 1answer 375 views ### Genetic algorithm - fit max circles inside box - what chromossomes? I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y ... 1answer 236 views ### A problem similar to the Bin packing problem? I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is: Given n items, each with ... 1answer 115 views ### route and/or packing optimization algorithm What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it? Given: a list of items each with a ... 1answer 218 views ### Packing sets to maximize overlap We are given a set of$m$elements$\{e_1,...,e_m\}$that form our universe$\mathcal{U}$. Each element of our universe is further associated with a positive weight$w(e_j)$with$j\in \{1,...m\}$. We ... 0answers 109 views ### Hexagon packing algorithm I'm trying to pack hexagons, within bigger hexagons, as shown here: For this example, I have 5 "children" to put in my "father" hexagon. Each time I've got too many children, I would like to reduce ... 0answers 45 views ### Packing the edges of a graph Given a graph G, and positive integers k, q, pack the edges of G in (pairwise edge disjoint) connected sub-graphs, each of size (number of edges) at most k, and such that, no vertex is part of more ... 0answers 109 views ### Equally distributed/packed spheres within a sphere I need to equally distribute a variable number of spheres within a larger sphere (the volume of the spheres depends on how many there are). Are there any algorithms for doing this? An approximate ... 2answers 3k views ### Algorithm for packing various shapes inside of a rectangle Say I am given a rectangle of width$W$and length$L$. I now have to fit as many regular shapes of area$A$into this rectangle as possible. For example, if the shape is a circle, I need to fit as ... 1answer 291 views ### Reducing 3 SAT to 3 SET PACKING I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ... 1answer 2k views ### Does a greedy strategy exist for this instance of the Bin Packing Problem? I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ... 1answer 22 views ### Optimal way to pack items with multidimensional weight such that the number of items is minimized? I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, ... 1answer 67 views ### packing with time-variant weights This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions. Scenario 1: Tough (for me!) There is a one day conference with a set of (4 or ... 1answer 58 views ### Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40) How would I find the maximum possible size of S, where S is a ... 1answer 252 views ### Bin packing with item weight constraint In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w_a1,...,w_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the ... 1answer 669 views ### How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint? The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of ... 1answer 63 views ### Group values up to a threshold and minimize groups Given a threshold$t$and a list of numbers$N$.$\forall n \in N: n \leq t$Now group the numbers so that the sum of the numbers$s$is lower or equal$t$. Minimize the amount of groups. Example:$...
Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$. For ...