4
votes
Accepted
Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?
EDIT: Merged the two answers.
Here's the problem statement:
The input is $(V, \mathbf b, \ell)$, where $V=\{x_1,x_2,\ldots,x_n\}$ with each $x_i\in\{0,1\}^d$ (where $d$ is constant), vector $\textbf{...
- 9,595
4
votes
Accepted
Complexity of Finding Optimal Synergistic Set Packings
This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's ...
- 1,419
3
votes
Accepted
The "electricity packing" problem
Here is an elaboration of my comment. From what I can understand, the OPs problem can be cast as the solution of a large implicit linear program. Given the $n$ numbers $d_1,d_2,\ldots,d_n$ let $\...
- 6,979
3
votes
Accepted
Does the following type of hitting problem have a name?
I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph $G=(A;B,E)$...
- 1,642
2
votes
Accepted
Scheduling to maximize idle time
Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.):
Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time ...
- 1,026
2
votes
Is the following problem NP hard?
Lemma. The problem is NP-hard.
Proof sketch. We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,...
- 9,595
2
votes
Accepted
Packing $n$ objects into $m$ bins whose size is variable
One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows.
Let $c=(\sqrt{17}-1)/2 \approx 1.56$.
There are three objects of size $c$, $1$, and $1$.
...
- 18.9k
2
votes
Partitioning a square for optimal queries
A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up ...
- 21
2
votes
$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)
Using Chandra's hint, I think I got the idea. We bounded the probability:
$$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$
Now consider an item of size $s_i$ that was left. It was ...
- 1,058
1
vote
Packing sets to maximize overlap
I believe it's NP-hard, by a reduction from min-balanced cut. Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each ...
- 9,595
1
vote
How to continue this algorithm?
A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that ...
- 1,046
1
vote
Packing $n$ objects into $m$ bins whose size is variable
This seems similar to bin-packing problem.
I set $a=1$ and try to solve the bin-packing problem of putting objects of size $O_1$ to $O_n$. If I cannot find the solution then I increase $a$ with value $...
- 199
Only top scored, non community-wiki answers of a minimum length are eligible