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

-1
votes
1answer
16 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
60 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
74 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 ...
6
votes
0answers
83 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 ...
3
votes
1answer
45 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 ...
7
votes
3answers
286 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
36 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 = ...
1
vote
1answer
25 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
136 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 ...
2
votes
0answers
35 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
410 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
74 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
134 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
291 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
42 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
81 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 ...
5
votes
2answers
1k 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 ...
14
votes
1answer
127 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 ...
5
votes
1answer
1k 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 ...
7
votes
1answer
218 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 ...
18
votes
1answer
744 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 ...
5
votes
0answers
774 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 ...
18
votes
2answers
733 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 ...