1
$\begingroup$

I would like to know how to prove that the Job Scheduling decision problem is strongly NP-complete using 3-partition.

Input: A set of $n$ tasks of length $t_1, t_2, \ldots t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha: \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$ which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.

In the JS$_{dec}$ decision problem corresponding to JS, the instance is accompanied by a target value $T$ and we are trying to find out if there is a solution where all the processors have a usage time limited by $T$.​

$\endgroup$
1
$\begingroup$

Let $X = \{x_1, \dots, x_n\}$ be an instance of $3$ partition where $n$ is a multiple of $3$ and each $x_i$ is strictly between $\frac{3}{4n}\sum_{i=1}^n x_i$ and $\frac{3}{2n}\sum_{i=1}^n x_i$. The problem remains NP-hard even with this restriction.

The instance of the job scheduling decision problem has $n$ jobs, $t_i = x_i$, $k=\frac{n}{3}$, and $T=\frac{3}{n}\sum_{i=1}^n x_i$.

If the 3-partition instance is a "yes" instance, then there is a partition of $X$ into $\frac{n}{3}$ sets $X_1, X_2, \dots, X_{\frac{n}{3}}$ such that, for each $j=1, \dots, \frac{n}{3}$, $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$. Let $\alpha(i)$ be the index $j$ of the unique set $X_j$ containing $x_i$. Then $\alpha$ is an assignment for the job scheduling instance in which, for each $j=1,\dots,\frac{n}{3}$, $u_j = \sum_{i : \alpha(i)=j} = \sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i = T$. This shows that the job assignment instance is a "yes" instance.

If the job scheduling instance is a "yes" instance, then let $\alpha$ be a corresponding assignment. For each $j=1,\dots,\frac{n}{3}$:

  • $|\{i : \alpha(i)=j\}| \le 3$, as otherwise $u_i > 4 \cdot \frac{3}{4n}\sum_{i=1}^n x_i = T$.
  • $|\{i : \alpha(i)=j\}| \ge 3$, as otherwise $u_i < 2 \cdot \frac{3}{2n}\sum_{i=1}^n x_i = T$, implying that $\max_{j' \neq j} u_j \ge \frac{\sum_{i=1}^n x_i - u_i}{\frac{n}{3}-1} > \frac{\sum_{i=1}^n x_i - T}{\frac{n}{3}-1} = \frac{\frac{n-3}{n}\sum_{i=1}^n x_i}{\frac{n-3}{3}} = \frac{3}{n}\sum_{i=1}^n x_i = T$.

As a consequence, the sets $X_1, \dots, X_{\frac{n}{3}}$, where $X_ j = \{x_i : \alpha(i)=j\}$, contain $3$ elements each and form a partition of $X$. Moreover, $\sum_{x \in X_j} x = u_j \le T = \frac{3}{n}\sum_{i=1}^n x_i$ and an argument similar to the one above shows that $\sum_{x \in X_j} x \ge \frac{3}{n}\sum_{i=1}^n x_i$. This proves that $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$ and hence that the $3$ partition instance is a "yes" instance.

$\endgroup$

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.