Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
1answer
131 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
50 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
40 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
33 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
18 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
24 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
38 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
163 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
82 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 ...
6
votes
1answer
1k 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
106 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
245 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
25 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
139 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
117 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
136 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
135 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
103 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
194 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 ...
2
votes
1answer
26 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
88 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
49 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
687 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
355 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
102 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
50 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
410 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
100 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
137 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 ...
6
votes
1answer
96 views

Dividing bins into segments

This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer. Consider the problem of dividing $p n$ bins numbered $1$...
6
votes
0answers
220 views

What's the complexity of solving a packing LP?

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in ...
4
votes
1answer
270 views

What is the sqrt(n)-approximation algorithm for set packing problem

The set packing problem is : Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of ...
9
votes
3answers
1k views

How to solve an arrangement problem at the Archive Nationale of France using graph theory?

Good evening! I'm actually doing an internship at the Archives Nationales of France and I encountered a situation I wanted to solve using graphs... I. The dusty situation We want to optimize the ...
2
votes
1answer
155 views

Balanced weight distribution in buckets, with different weight per bucket

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,......
1
vote
1answer
35 views

Term clarification: Establishing a domination

In the book "Approximation Algorithms" by Vazirani (legally available online), part of the hint to Exercise 9.6 (on page 77 of the book, page 95 of the PDF) says "Establish a domination". I've never ...
4
votes
1answer
157 views

Bin packing with twin items

Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no ...
3
votes
1answer
205 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$ ...
2
votes
0answers
43 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 ...
3
votes
1answer
2k views

How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves (...
2
votes
0answers
106 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 ...
4
votes
2answers
440 views

Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
1
vote
1answer
946 views

How can we design an efficient warehouse management program?

Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box ...
4
votes
0answers
56 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
2
votes
1answer
176 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 ...
8
votes
2answers
5k views

Equivalence of independent set and set packing

According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent. The Independent Set search problem is: given ...
17
votes
1answer
189 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 ...
8
votes
1answer
3k views

Is the 0-1 Knapsack problem where value equals weight NP-complete?

I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-...
7
votes
1answer
399 views

Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin. Is there an ...
20
votes
1answer
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 ...
6
votes
0answers
1k views

Relations between the knapsack problem, the bin packing problem, and the set packing problem?

I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem? From their mathematical formulations, I don't see the first two belong to the third one ...