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$
  • $\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 Jan 24 '18 at 21:19
  • $\begingroup$ @Discretelizard i edited my question $\endgroup$ – Pedro Vaz Pimenta Jan 24 '18 at 22:34
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, privacy policy and cookie policy

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