Polynomial-Time reduction from Partition to MakeSpan

Question

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.

Answer 1

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 \}$.