1
$\begingroup$

The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple exact algorithm - checking all the possible partitions - takes time $O(n 2^n)$. Is there a more efficient exact algorithm?

NOTE: If the numbers are small integers, then it can be solved by a pseudo-polynomial algorithm, but I am interested in a problem with real numbers (e.g. "double"s in Java).

$\endgroup$

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.