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.

Filter by
Sorted by
Tagged with
0
votes
0answers
9 views

Proof of lemma for competitive ratio on subsequence - Strip Packing

In this paper by Azar and Epstein in Section 4 they consider online strip packing of rectangles without rotation in a setting where when a rectangle arrives it has to be lowered monotonically ...
0
votes
1answer
31 views

Bin packing problem and optimality proof

Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
0
votes
0answers
7 views

Looking for algorithm to pack rectangular squares while considering locality

I have a couple of rectangles (~10'000 - 1'000'000) with various integer dimensions where each side is something between 1-10 I got to arrange these (without rotating) into a block of fixed width ...
7
votes
1answer
100 views

What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
6
votes
2answers
194 views

Can this special case of bin packing be solved in polynomial time?

Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$. Is there a polynomial-...
0
votes
1answer
34 views

What's the name of this packing problem?

I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping. For example if I have these intervals: ...
2
votes
1answer
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 ...
4
votes
1answer
73 views

Bin packing when items can be broken

In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break ...
0
votes
0answers
26 views

Packing a sphere with cuboids

This question on the Mathematics SE addresses how to pack a sphere with unit cubes. This addresses how to pack a 2D grid with rectangles. We can pack a sphere with the minimum number of unit cubes $m$ ...
4
votes
1answer
131 views

One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
0
votes
1answer
21 views

Bin packing variant for maximizing value in a bin

I'm creating a tool where, given a list of N items that have a volume (v) and a price (p), ...
1
vote
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, ...
1
vote
0answers
17 views

Additive approximation to bin packing

The bin packing problem is an NP-hard optimization problem that has many constant-factor approximation algorithms. I am looking for an additive approximation. I.e., given a set $I$ of items and bin ...
0
votes
0answers
69 views

offline Bin Packing problem with multiple size bins

As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard. here are the ...
0
votes
1answer
57 views

Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

I explain it better: There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time. An example is Bin Packing, the decision ...
0
votes
1answer
40 views

Approximate bin-packing?

Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
0
votes
0answers
17 views

Pack Paths [Concave and Convex]

I would like to design an algorithm to pack closed paths into a rectangle. An example of one of these paths is below: The rectangle will have a fixed width, but the height will expand to accommodate ...
3
votes
0answers
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 ...
1
vote
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 ...
2
votes
0answers
106 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 ...
1
vote
1answer
263 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 ...
4
votes
1answer
445 views

Greedy algorithm Packing problem

Assume that $A$ is the set of objects such that each object $x_i \in A$ has value $w_i$. We wish to pack these objects into group, each pack containing at least $k$ objects. Our goal is to minimize ...
0
votes
0answers
59 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
0
votes
0answers
142 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
3
votes
1answer
54 views

How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?

Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded /...
1
vote
1answer
49 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 ...
0
votes
0answers
37 views

For a given shape, find set of points with the maximum average distance

Within some shape, I want to find a set of points where the distance between each point is maximized. This seems similar to sphere packing to me except that part of the sphere can be outside the shape....
3
votes
1answer
57 views

Constructing an optimal solution to bin packing using a "magical function" $\phi$

I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem. Consider the bin packing problem, with objects of positive (rational) weights $W = \{...
2
votes
1answer
370 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 ...
0
votes
2answers
123 views

Genetic Algorithm - Fit max circles inside box

I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation ...
7
votes
1answer
4k views

Fitting different rectangles inside a rectangle

I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes. I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate ...
1
vote
1answer
249 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 ...
1
vote
1answer
652 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 ...
1
vote
1answer
61 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: $...
1
vote
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 ...
1
vote
2answers
141 views

Non-trivial bin-packing instance with 5 objects

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 ...
2
votes
1answer
225 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 ...
1
vote
0answers
248 views

Job scheduling and packing algorithm

I was thinking about developing a daily production work plan algorithm for an enterprise. The problem is as following: There are various tasks that needs to be completed, each has a deadline, a ...
1
vote
0answers
116 views

Schedule repeating jobs of fixed length and different weights

I have a scheduling problem that I am not sure is a known variant with known algorithms. It does appear like bin packing problem at first, but after imposing the constraints, I am not sure what it ...
0
votes
1answer
311 views

What does a solution to the Rectangle-Fit problem look like?

I've been learning about NP-Complete problems, and came across the rectangle fit problem. Basically, the rectangle-fit problem is the problem of whether or not a set of 2d rectangles can fit in a ...
3
votes
1answer
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 ...
2
votes
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 ...
0
votes
1answer
65 views

How can i fill shelves with products so that I have the maximum amount of sales?

I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales ...
1
vote
1answer
1k 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 ...
12
votes
1answer
384 views

Is packing a bag of presents easier for Rupert than Santa?

Or: Do we need Rupert in order to get presents at all? Routing issues aside, Santa faces the following problem (many, many times over): Given a bag with capacity¹ $C$ and a set of presents $\{p_1, \...
4
votes
0answers
125 views

Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
0
votes
1answer
65 views

Help me identify the type of Knapack Problem I am dealing with

I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the ...
3
votes
1answer
562 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 ...
-1
votes
1answer
122 views

ordered uniform distribution

We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ ...
2
votes
1answer
216 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 ...