[Solved]: Reduction from partition to multiprocessor scheduling

Problem Detail: 

I am kind of unsure about a reduction between two problems. Here are the two problems:

PARTITION: Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$. Question: Can the set $S$ be partitioned into two subsets $S_1$,$S_2$, s.t. the sum of the numbers in $S_1$ equals the sum of the numbers in $S_2$?

MULTIPROCESSOR SCHEDULING: Instance: A set $J$ of $k$ jobs where job $j_i$ has length $l_i$, and $m$ processors. Question: Can we schedule all jobs in $J$ on $m$ processors s.t.: (a) on each processor the next job in the sequence is started immediately after the preceding job is finished and (b) the total time to execute all jobs on each processor takes the minimum possible time $T_{min}=\big(\sum\limits_{i=1}^k l_i\big)/m$

I am a little bit unsure about my try to reduce Partition to multiprocessor scheduling. My attempt is posted as an answer.

Asked By : user1291235

Answered By : FrankW

(This is the answer that the OP wanted to have checked.)

Let $S=\{a_1,...,a_n\}$ be an arbitrary instance of Partition. In our reduction we set $J=S$. if $\sum\limits_{a \in S} a$ is even, we set $m=2$. Note: If the sum of elements in $S$ is odd, there cannot be a Partitioning. Further, we set the length $l_i$ of job $j_i$ to the value of $a_i$.

So this is my reduction. But I am very unsure if this is just too easy? Note that I do not have to provide the correctness proof but just the reduction. Is this somehow a right reduction? I am very unsure if I have to distinguish between the two cases where the sum of elements of $S$ is odd or even. What if the sum is odd?

Can someone give me some hints on that?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24610