Hot answers tagged

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{...
Neal Young's user avatar
  • 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 ...
Andrew Morgan's user avatar
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 $\...
Chandra Chekuri's user avatar
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)$...
Yonatan N's user avatar
  • 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 ...
Thomas Kalinowski's user avatar
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,...
Neal Young's user avatar
  • 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$. ...
András Salamon's user avatar
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 ...
user50253's user avatar
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 ...
user3508551's user avatar
  • 1,078
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 ...
Neal Young's user avatar
  • 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 ...
Stella Biderman's user avatar
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 $...
Masood_mj's user avatar
  • 199

Only top scored, non community-wiki answers of a minimum length are eligible