0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have moved your attempt to an answer, because that fits the site format better. I will comment there about correctness/improvements. $\endgroup$ – FrankW May 12 '14 at 8:14
0
$\begingroup$

(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?

$\endgroup$
  • $\begingroup$ The reduction is basically correct. You do not need to make a case distinction for odd sum: In that case the reduction will give an instance that cannot be scheduled, just as needed. $\endgroup$ – FrankW May 12 '14 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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