0
$\begingroup$

Perfect partition problem (PPP): given $x_1,...,x_n\in \mathbb{N}$ we want to know if there's a set $S\subset \{1,2,...,n\}$ such that $$\sum_{i\in S}x_i=\sum_{j\notin S}x_j.$$

Single machine task schedule problem (SMP): a machine can perform only one task $T_i$ with duration $d_i$ at a time and we want to know if all tasks can be done, given that $T_i$ can't start before the time $a_i$ or be finished after the time $b_i$ with $i\in \{1,2,3,...,n\}$.

I want to know how to reduce PPP to SMP.

EDIT: I tried modelling SMP using the constraints and the existence of a bijection $f:\{1,2,3,...,n\} \rightarrow \{1,2,3,...,n\}$ such that $$a_{f(i)}\leq \sum_{j=1}^i d_{f(j)}\leq b_{f(i)}$$ for all $i\in \{1,2,3,...,n\}$. And I tried to make $x_i=d_i$ and get the conditions of the SMP to make the sum be equal to que complementary $\left (\frac{\sum_{i=1}^{n} x_i}{2}\right)$ at some point, but I got stuck as I can't find how to relate $f$ to $S$ from the PPP, that's not really working.

$\endgroup$
2
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. $\endgroup$
    – Discrete lizard
    Commented Jan 24, 2018 at 21:19
  • $\begingroup$ @Discretelizard i edited my question $\endgroup$ Commented Jan 24, 2018 at 22:34

1 Answer 1

1
$\begingroup$

Just let $d_i=x_i$, $a_1=\frac{\sum_{i=1}^n x_i}{2}-d_1$ and $b_1=\frac{\sum_{i=1}^n x_i}{2}$, and $a_i=0$ and $b_i=\sum_{i=1}x_i$ for other $i$'s. Then easy to see there is a solution for the original PPP instance iff there is a solution for this SMP instance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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