# Tag Info

11

We can reduce the no-rotations packing problem to the rotations-allowed packing problem as follows. Take any instance $(R, r_1, r_2, \dots, r_n)$ of the no-rotation problem. Vertically scale the entire instance by twice the ratio of the smallest width of any rectangle $r_i$ divided by the height of the container rectangle $R$. (This ratio has a polynomial ...

10

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 ...

9

There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search. I think you can use the same ...

8

Your problem is the multiple knapsack problem. Although I am not familiar with this problem, I believe you'll find some papers on your problem, since there are many papers on this problem (see for example a SODA 2009 paper)

5

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta>0$, the Bin Packing problem is NP-hard when $1/3-\delta < a_i$ for all $i$.

5

Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate. Read this paper for more information: Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378

4

I started a project under MIT license to try to solve this problem. Currently it uses the 'best fit' approach. Sorts 'items' from largest to smallest and sorts bins from smallest to largest. Finds first bin that is large enough to use that has ALREADY been used (if possible). Let's see if we can make it a good enough solution for all. https://github.com/...

4

As mentioned in the comments, the problem is called the (2-dimensional) packing problem. Your problem (Rectangle packing) is NP-complete. It can be shown with a reduction from the Bin Packing problem. See for example this paper Richard E. Korf: Optimal Rectangle Packing: Initial Results. Here's a link that describes an algorithm (the same basic idea as in ...

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 ...

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 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 On the positive side, there is a$\mathsf{OPT} + O(\log n)$approximation (as opposed to the$\mathsf{OPT} + O(\log^2 n)$approximation known for general bin-packing): either using the Karmakar-Karp rounding of the Gilmore-Gomory relaxation of bin packing (check David Williamson's book), or, more recently, using the connection with discrepancy of ... 2 The first-fit algorithm is a greedy algorithm that states "For each item, it attempts to place the item in the first bin that can accommodate the item". 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 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 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 ... 1 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 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 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 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. 1 Perhaps the corresponding decision problem is NP-complete; given an instance of SUBSET-SUM: Given$K, x_1,...,x_n$does exist$A \subseteq \{x_1, x_2, ..., x_n\}$s.t.$\sum_{x_i \in A}x_i = K$? Suppose that$k > 0, x_i > 0$and let$k' = \sum_{i=1..n} x_i - K$Now, if you pick two bins$B_1, B_2$with sizes$k$and$k'$, then$n$items of sizes$...

1

As mentioned by snowie, your problem is a generalization of the sharing-aware virtual machine colocation problem, and is hard to approximate. Read this paper for more information: Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378 The paper shows hardness for the general ...

1

So, each object is a set and the size of a collection of objects is the size of their union, right? I don't have a proof, but my guess is that the problem is hard/difficult. Here's why: One special case of the problem is this: when all objects correspond to sets of size 2, then we have the following graph problem (each object corresponds to an edge of the ...

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