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.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
310 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 ...
user1742364's user avatar
6 votes
0 answers
2k 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 ...
Tim's user avatar
  • 4,895
4 votes
0 answers
135 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 ...
Dong  Deng's user avatar
4 votes
0 answers
68 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 ...
user12486's user avatar
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
2 votes
0 answers
30 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
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
2 votes
0 answers
247 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
2 votes
0 answers
47 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 ...
Selma's user avatar
  • 21
2 votes
0 answers
113 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 ...
Flex Elektro Deimling's user avatar
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
1 vote
0 answers
71 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
0 answers
37 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
1 vote
0 answers
264 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
1 vote
0 answers
126 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 ...
nepee's user avatar
  • 280
0 votes
0 answers
61 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
0 votes
0 answers
201 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
0 answers
52 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
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
0 votes
0 answers
49 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