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.

learn more… | top users | synonyms

2
votes
0answers
30 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
47 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 ...
4
votes
2answers
187 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 ...
6
votes
0answers
67 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 boards of raw glass, of width W and ...
4
votes
1answer
444 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 ...
5
votes
0answers
56 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 ...
17
votes
1answer
382 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 ...
2
votes
0answers
296 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 ...
15
votes
2answers
503 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 ...