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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Try $r=2$ and $G$ which is half the total sum. $\endgroup$
    – Yuval Filmus
    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$
    – Yuval Filmus
    Dec 2, 2019 at 23:38
  • $\begingroup$ Are G and r constants? $\endgroup$
    – Narek Bojikian
    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$
    – Narek Bojikian
    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$
    – Yuval Filmus
    Dec 2, 2019 at 23:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ If $r > 1$ is fixed ahead of time, simply add $r-2$ many copies of $k$. $\endgroup$
    – Yuval Filmus
    Dec 3, 2019 at 0:04
  • $\begingroup$ Yes that should work :) $\endgroup$
    – Narek Bojikian
    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$
    – Narek Bojikian
    Dec 3, 2019 at 19:34

Your Answer

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

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