Hot answers tagged

9

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts. Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\...


7

I think I have a solution to your problem. Hopefully I haven't misunderstood something in the definition of your problem. Here it goes: I'm going to describe a Dynamic Programming approach. It's an $O(n^{2})$ algorithm, which means that since the number of books is huge it's not going to help you a lot. (you need to modify it a bit!). With some work, you ...


7

The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems. You've demonstrated what's known as a parsimonious reduction between the two problems. Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property ...


5

I see you as asking, "I want to solve this with Dijkstra's algorithm but I can't set up a good graph to run on," therefore I will present you with such a graph. A digraph where vertices are sets of shelved books. Okay, we have books with heights $H_n,$ $1 \le n \le N$ and widths $W_n,$ with heights in ascending order for each book, and we want to group ...


4

See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms: Unweighted case: Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998), "Independent sets with domination constraints", Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185. Weighted case: ...


4

The problem is NP-complete because it is in NP and captures the partition problem with $n = 2$ and $m = \frac12 \sum_{i = 1}^q{w(o_i)} - \frac12 \min_{i}w(o_i)$. If an equal weight partition exists, then the items can be packed in two bins each of weight $\frac12 \sum_{i = 1}^q{w(o_i)}>m$. If it doesn't, then one of the two bins would have weight at most $...


3

I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below. Multiple bookcases If you have multiple bookcases, and you need to put each shelf into exactly one of the bookcases, then you have an instance of the bin packing problem. Each shelf corresponds to an item, and each bookcase corresponds to ...


3

Both problems are NP-complete, so even without checking your reductions, they are equivalent in that sense. However, your reduction does seem okay. Technically for approximation results you want to verify some additional properties of the reduction (not necessarily hard to do, e.g. in this case PTAS reductions are of interest). You also have to talk about ...


3

This belongs to an optimization class of problems called Packing problems. In your case, instead of a regular polygon as container, you've got an irregular one, but the idea remains the same. These optimization problems are usually NP-hard, so I don't think there is an easy way to get the exact solution and trying all the combinations would be too too ...


3

As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions. A lot approaches ignore rotation, but can ...


3

If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails. Let $G = (V, E)$ be an undirected graph with $n$ vertices $v_1, \dots, v_n$ and $m$ edges $e_1, \dots, e_m$. Construct an instance of your problem by creating $n'=n$ groups as ...


3

Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size. Consider an instance of $3$-partition in which $3n$ positive integers $x_1, x_2, \dots, x_{3n}$ of total sum $...


2

This problem is known as Unrelated Parallel Machine Scheduling. Minimizing $max_j T(b_j)$ has a 2-approximation, by LP-relaxation and rounding.


2

Let $(U,S,k)$ be an instance of Set Packing where $U$ is base set, $S$ is the collection of sets over $U$ and $k$ is the minimum size of the desired set packing. We can construct an instance of Erel's Set Packing (nice name, no? ;) ) by taking $k$ copies of $S$ (i.e. $n=k$, $M=|S|$), label them $S_{i}$ for $1\leq i\leq k$. Then if $(U,S,k)$ has a set ...


2

No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a solution for your problem in polynomial time using a greedy approach. Then, you could use your algorithm to solve in polynomial time the decision version of the ...


2

As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete. Skiena Section 17.9 reports: Fortunately, relatively simple heuristics tend to work well on most bin-packing problems. The same source provides the following heuristic recommendation: Analytical and empirical results suggest that first-fit ...


2

For $0 \leq i \leq pm+1$, define $$ x_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor. $$ We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) is $$ x_i - x_{i-1} = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor - \left\lfloor (i-1) \frac{pn+1}{pm+1} \right\rfloor \in \left\{ \left\lfloor \frac{pn+1}{...


2

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.


2

P is in big-endian format. P0 —0111011011010011001011010010011001011001010010001011011010000001, The first bit, 0, means 2*0 + 1 = 1 is not a prime. The second bit, 1, means 2*1 + 1 = 3 is a prime. The third bit, 1, means 2*2 + 1 = 5 is a prime. The fourth bit, 1, means 2*3 + 1 = 7 is a prime. The fifth bit, 0, means 2*4 + 1 = 9 is not a prime. The sixth ...


2

Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).


2

I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it. Let $c_1, \dots, c_n$ be the series data. For each valid start time $i$, create a variable $x_i$ to hold the number of copies to start at this time and add the constraint $x_i \ge 0$. For each minute of time $i$ (now ...


2

Yes, there is a polynomial time solution. It is not very pretty, so simplifications or alternative approaches are welcome. TL;DR: the exact weights are rarely important, so we can round them up to a multiple of $K := \lceil \frac{3M}{n^3} \rceil$ or something similar (there are only $\approx n^3$ rounded item weights). Then, we can do dynamic programming ...


1

In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of weights of these objects. But, in cuboid/rectangle packing problem the configuration of the cubes/rectangle is important to achieve the optimal packing. So, from ...


1

I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.


1

The problem for shapes of general form is in the class of NP-Hard, so there is nos efficient algorithm to solve this problem. Bin packing is a well known class of problems. The approach will depend on your intentions: Need a complete algorithm, i.e. an algorithm that compute the correct solution for the problem but can only compute small instances of your ...


1

Let's look at two algorithms: Best Fit Ordered, and First Fit Ordered. Both take the items in descending order and put them into a non-empty bin if possible, or into a new empty bin if they don't fit into any existing bin. Best Fit Ordered puts an item into the filled bin with least available space, First Fit Ordered puts an item into the first filled bin ...


1

One way to solve your problem is to use binary search over the maximum weight. In other words, pick a threshold $t$, and check whether it's possible to pack your items into $m$ bins, without using more than a total weight of $t$ in each bin. This is exactly the bin packing problem: is it possible to pack the items into $m$ bins of capacity $t$? You can ...


1

You can simply list the coordinates of the upper-left corner of each rectangle (and its orientation, if you're allowed to rotate rectangles). That completely determines its position, and thus listing that for all rectangles completely identifies the configuration of all rectangles.


1

The bins contain at most $M$ elements rather than exactly $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$. As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain ...


1

This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', which are the delivery requests. We look for an assignment of tasks to workers that minimizes the time until the last worker is finished, the makespan of the ...


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