# Tag Info

11

Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a ...

4

Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min_{i,j} b_i/A_{i,j}$ (which we can assume is at least $1$). If $A$ ...

4

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 lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's ...

4

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{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$, and $\ell$ is an integer. The problem is to decide whether $V$ can be partitioned into $\ell$ parts $V_1,V_2,\ldots,... 3 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)$, with each of$A$and$B$sub-partitioned into a collection of equal-sized so-called supervertices. A superedge between two supervertices$a,b$is the set ... 3 The previous reduction doesn't work with the current reformulation of your problem (19 July 2014); however I leave it below, because it is correct for that particular maximum k-set packing problem variant (which is defined in the reduction). Here it is a fix for the current version: CURRENT VERSION Again your problem is NP-hard for$l \geq 3$. NOTE that$...

3

I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (...

2

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,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, ...

2

I found a related MS thesis. Title: APPROXIMATION ALGORITHMS FOR MINIMUM KNAPSACK PROBLEM https://www.uleth.ca/dspace/bitstream/handle/10133/1304/islam,%20mohammed.pdf?sequence=1 You can also find related papers in its references.

2

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 scheduling to minimize machine busy times. Journal of Scheduling 18(6), 561-573, 2015. doi:10.1007/s10951-014-0411-z In particular, their results give a polynomial time ...

2

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$. There are two bins of size $2$ and $c$. Initially $a=1$. Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at ...

2

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 to $C = 0.907$ coverage. Assuming the scittles are uniformly distributed and $N \gg \frac{1}{S_c}$, where $S_c$ is the surface of the cricles you use, we may ...

1

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 side), and cuts at most $\ell$ edges. Given $G$ and $\ell$, construct the following instance of your problem. For each vertex $v$, create a set $S_v$ ...

1

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 form allowable rectangles. Ennumate them and try all the options. This is pretty bad, but unless you're going to do something more clever than "try all the ...

1

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 $\delta >0$ and try again. If it doesn't work I increase $a$ by $2\delta$ and so on.

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