1

Are these two problems isomorphic to each other? — (1) Finding the position in an array that splits it into two partitions minimizing the maximum of the sum between the two partitions. (2) Finding the position in an array that splits it into two partitions minimizing the absolute value difference of the sums of the two partitions.

It intuitively seems that both these problems essentially want the sums of the two partitions to be as close to each other as possible.

However, the former seems to have a O(lg N) solution through binary search while the latter is the NP-Complete partition problem, only having a pseudo-polynomial time dynamic programming algorithm.

Is there a case where the partition point for these two problems would not be the same?

1110101001
  • 4,662
  • 7
  • 26
  • 48
  • I'm an idiot. The partition problem allows selecting non-consecutive elements for each subarray (more like a subsequence but whatever). Whereas the minimize maximum problem linked allows only consecutive subarrays. – 1110101001 Jul 30 '16 at 20:39

0 Answers0