2
$\begingroup$

I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.

Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it possible to arrange the pens where each row has a maximum length G, where G is the minimum possible.

I have shown that this problem is in NP, but now I'm trying to reduce a subset sum problem to this problem with karp reduction.

I know how the subset sum problem looks like, but I'm having a trouble where to start with the reduction, any tips would be greatly appreciated.

$\endgroup$
5
  • 1
    $\begingroup$ Try $r=2$ and $G$ which is half the total sum. $\endgroup$ Commented Dec 2, 2019 at 22:02
  • $\begingroup$ In order to check your answer, try proving that it works. If you're successful, then it works. You don't need me for that. $\endgroup$ Commented Dec 2, 2019 at 23:38
  • $\begingroup$ Are G and r constants? $\endgroup$ Commented Dec 2, 2019 at 23:45
  • $\begingroup$ Try reducing the two partition problem instead it is as easy and will help you go around some mathematical issues $\endgroup$ Commented Dec 2, 2019 at 23:50
  • $\begingroup$ Try to be resourceful. Also, it is really unclear from your post that $r$ is fixed rather than a part of the input. Please edit your post to reflect that (not by adding an "EDIT:" section, but by just correcting your post). $\endgroup$ Commented Dec 2, 2019 at 23:57

1 Answer 1

4
$\begingroup$

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given set.

However, In the subset sums problem, if you found a subset that sums to $k$ the rest will sum up to a number equal to $\sum_{a \in S} a -k$ which might be not equal to k and hence might generate a problem. An easy solution is to add one number to set, namely $\sum_{a \in S} a - 2k$. And change k onto$\sum_{a \in S} a - k$. By this changes we turned the subset some problem into the two partitioning problem, where we are looking for a subset of the given set that sums up to half the sum of the elements in the setand hence, the rest of the elements have the same sum. After this step we canset the number of rows to two and the columns to the new value of $k$. Try to prove why this reduction works.

$\endgroup$
3
  • 1
    $\begingroup$ If $r > 1$ is fixed ahead of time, simply add $r-2$ many copies of $k$. $\endgroup$ Commented Dec 3, 2019 at 0:04
  • $\begingroup$ Yes that should work :) $\endgroup$ Commented Dec 3, 2019 at 0:06
  • $\begingroup$ Answering the first question, if $k >$ sum, then the instance is clearly a No instance and we can build any trivial No instance for the pens arrangement problem as the resulting instance from the reduction for example the instance $\{G+1\}$, since a pen with length $G+1$ does no fit in any row $\endgroup$ Commented Dec 3, 2019 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.