1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Steven Jun 12 at 11:31
  • $\begingroup$ Sry for the confusion, I want to to demonstrate Partition $\leq_{p}$ Makespan. $\endgroup$ – Syntaxizer Jun 12 at 11:36
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But how can I proof this on m machines? $\endgroup$ – Syntaxizer Jun 12 at 12:28
  • $\begingroup$ 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. $\endgroup$ – Steven Jun 12 at 12:44
  • $\begingroup$ 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. $\endgroup$ – Syntaxizer Jun 12 at 12:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Jun 12 at 12:57

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.