1
$\begingroup$

In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and $B/2$. This problem is strongly NP-hard.

The special case DISTINCT 3-PARTITION when all the integers are distinct has been studied here (at the end of the paper). The problem is also NP-hard in the strong sense. But in the definition of the instance, the authors do not include the condition that all the integers must strictly be between $B/4$ and $B/2$.

Is it clear that even with this condition DISTINCT 3-PARTITION is still strongly NP-hard? Thank you!

$\endgroup$
1
  • 1
    $\begingroup$ It's probably still NP-hard. Have you tried proving this? $\endgroup$ – Yuval Filmus Dec 20 '15 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.