I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:
Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains strongly NP-complete when every integer in S is strictly between B/4 and B/2.
Does this mean that if the multiset contains elements that fall outside the range B/4-B/2 the problem is no longer strongly NP-complete and admits heuristics or other optimizations? Am I interpreting that right?
Also am I correct in assuming that this problem (at least when it is strongly NP-complete) pretty much requires an exhaustive search (unless P=NP)?
I've sifted through some papers but haven't been able to figure this out.