10
$\begingroup$

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is feasible.

Let's take an example with $m=3$ numbers (with $b_1=1100$, $b_2=540$, $b_3=170$) and $n=2$ urns with capacity $C=4$. The problem consists to cut the $m$ numbers in order to have $nC$ parts. The cut must preserve each number, for example we have $nC=8$ parts by doing:

  • $b_1=100+400+450+150$.
  • $b_2=100+40+400$.
  • $b_3=170$.

Then we must place these $nC$ numbers in the urns (knowing that each urn has a capacity of $C=4$), for example:

  • Urn 1: $40$ (2) - $170$ (3) - $100$ (2) - $450$ (1)
  • Urn 2: $100$ (1) - $150$ (1) - $400$ (2) - $400$ (1)

The cost $f$ of any solution is defined as the sum of the biggest numbers in each urn, in this case: $f=450+400=850$.

The goal of the problem is to decide how to cut the numbers and how to gather them in the urns in order to minimize the cost (actually, I have no idea what is the optimal solution of the previous instance).

I am not looking for an algorithm to solve this problem but I am wondering if this problem is NP-hard. Maybe this problem can be linked with another combinatorial optimization problem ?

I already searched and all that I could find is that the problem is easy if $n=1$ (and we still assume $C \geq m$) and that there is a polynomial algorithm in that case.

Thank you very much!

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Perhaps start with a simpler problem: Assume that you have $nC$ numbers, to be distributed in $n$ urns where you want to minimize the cost, is this problem NP-hard, or significantly easier? $\endgroup$ Commented Jul 30, 2015 at 14:14
  • 4
    $\begingroup$ @PerAlexandersson, the cost per urn is the largest number in that urn, so that problem is trivial (order the numbers and take consecutive blocks of length $C$ for each urn). $\endgroup$ Commented Jul 30, 2015 at 14:56
  • 2
    $\begingroup$ Are the individual parts also required to be integers? $\endgroup$ Commented Jul 30, 2015 at 15:04
  • 7
    $\begingroup$ Here's a colourful rephrasing: you have $m \leq nC$ pieces of spaghetti and $n$ jars, each of which can hold $C$ pieces of spaghetti. Given that you are allowed to break the spaghetti if needed, what is the smallest total height of the jars such that you can put all of the spaghetti inside the jars and still get the lids on? $\endgroup$ Commented Jul 30, 2015 at 15:10
  • 1
    $\begingroup$ @TimothyChow Actually yes because the $b_i$ represent the number of 'balls', 'coins' (or whatever). Nevertheless, I am interested in any advice, even when the parts are real! $\endgroup$ Commented Jul 30, 2015 at 15:13

1 Answer 1

Reset to default
2
$\begingroup$

Edit Using 3-PARTITION instead of PARTITION in the reduction below, we get that the problem is strongly NP-hard.

I think we get NP-hardness by the following reduction from PARTITION. Let a PARTITION instance be given by positive integers $a_1,\ldots,a_N$ with $a_1+\cdots+a_N=2B$ where the question is if we can select an index set $I\subseteq\{1,\ldots,N\}$ with $\sum_{i\in I}a_i=B$. We define an instance of the spaghetti cutting problem with the following data

  • number of jars: $n=N$
  • jar capacity: $C=N+2$
  • number of spaghetti pieces: $m=N(N+1)+2$
  • spaghetti lengths: For each $i\in\{1,\ldots,N\}$, there are $N+1$ pieces of length $a_i$, and in addition there are 2 pieces of length $B$.

The trivial lower bound for this instance is $(\sum_{i=1}^mb_i)/C=2B$, and I claim that it can be achieved if and only if the PARTITION instance is a YES-instance. The "if"-part is obvious: You can cut the two pieces of length $B$ into $N$ pieces with lengths $a_1,\ldots,a_N$, and then we have one jar full of length $a_i$ pieces for every $i$. For the "only if" part it helps to assume $a_1>a_2>\cdots>a_N$ which is no problem (see here). In order to achieve the objective value $2B$ we need one jar full of pieces of length $a_1$, so we have to cut a piece of length $a_1$ from one of the two long spaghetti pieces. Then we can assume w.l.o.g. that we don't cut the pieces of length $a_1$. Next we need a jar full of pieces of length $a_2$, which can be achieved only by cutting it from one of the long pieces. Continuing in this way we complete the argument.

This leaves open what happens for bounded capacity $C$. The first interesting case is $C=2$, for which the question if the lower bound $(\sum_{i=1}^mb_i)/2$ is achievable can be formulated as follows: Given $b_1,\ldots,b_m$ and $n> m/2$, can we cut the $b_i$'s into $2n$ pieces such that every length appears an even number of times?

For what it's worth, here is a mixed binary programming formulation for the general problem: \begin{align*} \text{Minimize }\sum_{j=1}^n&x_{(j-1)C+1}\qquad\text{subject to}\\ x_1\geqslant &x_2\geqslant\cdots\geqslant x_{nC},\\ \sum_{k=1}^{nC}y_{ik} &= b_i &&i\in[m],\\ \sum_{i=1}^my_{ik} &= x_k && k\in[nC],\\ y_{ik} &\leqslant b_iz_{ik} && i\in[m],\ k\in[nC],\\ \sum_{i=1}^mz_{ik} &\leqslant 1 &&k\in[nC],\\ y_{ik} &\geqslant 0,\ z_{ik}\in\{0,1\} && i\in[m],\ k\in[nC]. \end{align*}

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.