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
1 answer
22 views

algorithm to categorize courses into academic degree requirements?

In most US universities, undergraduate students must satisfy the requirements of a degree program in order to graduate. The general rules are: The university has a minimum number of total credits ...
Foo Bar's user avatar
  • 536
1 vote
2 answers
26 views

strip packing problem with fixed x-coordinate

Similar to the classic 2D strip packing problem, we want to put N blocks into a 2d strip and minimize the height of the strip. Each block has to be put at the fixed x-coordinate. The width and height ...
Xiaotian Hu's user avatar
2 votes
0 answers
29 views

Online Bin Packing in 1D with Order Constraint

I have a computer science problem that seems relatively simple. We are given a number of 2D rectangles that we want to place next to each other on a 1D line (without rotating them). The 1D line has a ...
LTR's user avatar
  • 121
1 vote
0 answers
23 views

Approximation Algorithm for Bin packing Variant with Packing Overhead

I recently came up with this bin packing variant and was wondering, if someone has studied it before: Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
blackdra_gon's user avatar
0 votes
1 answer
64 views

Is the flexible bin packing problem NP-complete?

I am currently trying to figure out whether a flavor of the bin packing problem, which I call the "flexible bin packing problem" (F-BPP), is NP-complete. Here are the definitions for the ...
thunderbird30's user avatar
1 vote
1 answer
119 views

First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
TheCollegeStudent's user avatar
0 votes
0 answers
20 views

Original paper for a linked-list based circular packing algorithm

A circular packing algorithm to pack an array of radii roughly into a circle was implemented by someone else but they do not remember the paper in which they took the algorithm from. All I know is ...
GTHB317's user avatar
1 vote
1 answer
92 views

Ordered open-end knapsack problem optimised for minimum weight range

Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers preserving their original order in a way that minimises ...
matkins's user avatar
  • 113
1 vote
1 answer
68 views

Bin packing with more than one parameter

Usually, in bin-packing, we have objects of sizes $a_1,...a_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms. ...
Sandra's user avatar
  • 63
0 votes
0 answers
60 views

Bin Packing tight analysis lower bound?

I am having a problem understanding the following: This is the background of the lemma: To prove the lower bounds, we use the classical lower bound construction from [5, 9]. We have an input instance ...
ryan chandra's user avatar
5 votes
1 answer
624 views

Nesting algorithm for rectangular-based, fixed-orientation polygons

I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem). The main differences between this ...
bjornte's user avatar
  • 151
1 vote
0 answers
69 views

Algorithm for modified 2D irregular bin packing

So usually bin packing algorithms compute the tightest packed solution. I want to calculate the opposite, in my case the solution with the most space between the packed objects is needed. I tried ...
ItsMeTheBee's user avatar
1 vote
1 answer
379 views

Why is SET PACKING in NP?

I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that ...
Julie's user avatar
  • 13
2 votes
2 answers
168 views

Bin-packing with a capacity constraint on pairs of bins

In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum. ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
19 views

How to optimize the locations and orientations of a collection of irregular 3D objects?

I'm working on a project where I need to optimize both the locations and orientations of a collection of irregular 3D objects in a given simulation box. To optimize the locations and orientations ...
meTchaikovsky's user avatar
0 votes
1 answer
213 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 ...
Rob32409's user avatar
  • 115
8 votes
1 answer
168 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 ...
Erel Segal-Halevi's user avatar
6 votes
2 answers
410 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-...
Erel Segal-Halevi's user avatar
0 votes
1 answer
41 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: ...
Luca Spiller's user avatar
2 votes
1 answer
31 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 ...
Benjamin H's user avatar
4 votes
1 answer
107 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 ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
139 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 ...
Job Savelsberg's user avatar
0 votes
1 answer
25 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), ...
Colin Basnett's user avatar
1 vote
1 answer
28 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, ...
aisle3's user avatar
  • 13
1 vote
0 answers
33 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
191 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 ...
mhk's user avatar
  • 101
0 votes
1 answer
82 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 ...
Pur2all's user avatar
  • 18
0 votes
1 answer
53 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 ...
platypus17's user avatar
0 votes
0 answers
51 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 ...
Hackstaar's user avatar
  • 126
3 votes
0 answers
21 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 ...
feature_engineer's user avatar
1 vote
1 answer
76 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 ...
Konchog's user avatar
  • 113
2 votes
0 answers
233 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 ...
Vico's user avatar
  • 121
1 vote
1 answer
492 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 ...
Radosław Waśko's user avatar
4 votes
1 answer
579 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 ...
user avatar
0 votes
0 answers
64 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 ...
FollowK's user avatar
  • 11
0 votes
0 answers
162 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 ...
dezzeus's user avatar
  • 99
2 votes
1 answer
115 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 /...
Jonathan Komar's user avatar
1 vote
1 answer
119 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 ...
m00151's user avatar
  • 13
0 votes
0 answers
46 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....
John's user avatar
  • 1
3 votes
1 answer
77 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 = \{...
0ffset's user avatar
  • 33
2 votes
1 answer
657 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 ...
scottbear's user avatar
0 votes
2 answers
160 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 ...
scottbear's user avatar
8 votes
1 answer
6k 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 ...
Gary's user avatar
  • 81
1 vote
1 answer
383 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 ...
Gabb's user avatar
  • 13
1 vote
1 answer
822 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 ...
newfangs's user avatar
1 vote
1 answer
133 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: $...
Bernd Strehl's user avatar
1 vote
2 answers
6k 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 ...
wjmccann's user avatar
  • 549
1 vote
2 answers
167 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 ...
Adam Kurkiewicz's user avatar
2 votes
1 answer
293 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 ...
KshMny's user avatar
  • 21
1 vote
0 answers
263 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 ...
Hoàng Đình Thịnh's user avatar