Skip to main content
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
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
  • 10.8k
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
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
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,153
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
  • 10.8k
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
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

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