# Polynomial-Time reduction from Partition to MakeSpan

Partition Problem:

Input: $$A:=$$ {$$a_{1}, ..., a_{n}$$}. $$a_{i} \in \mathbb{N}$$ $$\forall i \in$$ $$\{1, \ldots, n\}$$.

Question: Exists a subset $$A_{1} \subset A$$ with: $$\sum_{a_{i} \in A_{1}} a_{i} = \sum_{a_{i} \in A\setminus A_{1}} a_{i}$$ ?

Output: Yes or No.

Makespan Problem:

Input: Jobs $$J$$ and $$b \in \mathbb{N}$$.

Question: Exists a Schedule $$S$$ with $$\text{FinishTime}(S) \leq b$$ ?

Output: Yes or No.

So I have to change the Makespan Problem in a way that the Partition Problem gives me the correct answers for the Makespan Problem. $$Partition \leq_{p} Makespan$$

First Problem: When the Makespan Problem has $$m$$ machines and not two, I don't know how I can use Partition for that scenario. I could recursive iterate the jobs (so that I split Makespan in several Partition Problems) but then I had to use the Partition Problem several times and with my understanding, I am only allowed to change the Input for a Polynomial-Time Reduction.

But let's say we have $$m= 2$$ machines. If Partition has the Output "Yes", I know that there exists an optimal solution for the Makespan, so that I have an optimal Schedule with value= $$\dfrac{1}{m} \cdot \sum_{a_{i} \in A}$$. If $$b \leq \dfrac{1}{m} \cdot \sum_{a_{i} \in A}$$, the result for Makespan is also Yes.

Second problem: But what happens if there is no optimal solution? I only receive "No" from Partition but I don't know how bad the Partition result is.

I would be really happy if someone has an idea for this, I don't know how to I could find a solution for this.

• Which direction are you looking for? In the title you write "Makespan to Partition", then in the question you write Partition $\le_p$ Makespan. Yet you also write "So I have to change the Makespan Problem in a way that the Partition Problem gives me the correct answers for the Makespan Problem". – Steven Jun 12 '20 at 11:31
• Sry for the confusion, I want to to demonstrate Partition $\leq_{p}$ Makespan. – Syntaxizer Jun 12 '20 at 11:36

Given an instance of partition (i.e., a set of numbers) $$\{a_1, \dots, a_n\}$$ create an instance of Job Scheduling (what you call Makespan) with $$2$$ machines and $$n$$ jobs $$j_1, \dots, j_n$$, where the execution time of the $$i$$-th job is $$a_i$$. Pick $$b = \frac{1}{2} \sum_{i=1}^n a_i$$.
If there is a solution to the partition problem, i.e., a set $$A \subseteq \{a_1, \dots, a_n\}$$ such that $$\sum_{a \in A} a = \frac{1}{2} \sum_{i=1}^n a_i$$, then there is a solution for the job scheduling problem: simply assign $$j_i$$ to machine $$1$$ if $$a_i \in A$$, and to machine 2 otherwise.
If there is a solution to the job scheduling problem, i.e., a partition of jobs into $$M_1$$ and $$M_2$$ such that $$\max\{ \sum_{j_i \in M_1} a_i, \sum_{j_i \in M_2} a_i \} \le b$$ then there is a solution $$A$$ to the partition problem. The choice of $$b$$ implies $$\sum_{j_i \in M_1} a_i = b = \frac{1}{2} \sum_{i=1}^n a_i$$, therefore it suffices to select $$A = \{a_i \, : \; j_i \in M_1 \}$$.
• You don't need to do that. You said that you want a reduction from Partition to Makespan, so it suffices to map each instance of Partition to one (suitably chosen) instance of Makespan. If you really want to have $m>2$ machines, then just add $m-2$ jobs with execution time $b$. The above reduction still works in this case. – Steven Jun 12 '20 at 12:44
• When I have Jobs with execution time $a_{1}= 1, a_{2}= 1, a_{3}= 2, a_{4}= 2, a_{5}= 3$ and $m= 3$. There exists no optimal solution for $m= 2$. But for $m= 3$ it exists an optimal solution. – Syntaxizer Jun 12 '20 at 12:55
• How is this relevant? You are just picking two random instances and showing that one has a solution while the other does not. To show the reduction from Partition to Makespan you need to prove that an instance $I$ of partition can be transformed in polynomial time to an instance $I'$ of Makespan such that $I$ has a solution if and only if $I'$ has a solution. This is what I have shown in my answer. – Steven Jun 12 '20 at 12:57