Given a set of finite numbers $X \subset \mathbb{R}$, we can partition $X$ into the upper half $U(X) := \{x|x \in X, x\gt median(X)\}$ and lower half $L(X) = \{ x| x \in X, x \lt median(X)\}$. As you can see, $L(X) \subset X, U(X) \subset X,L(X) \cup U(X) \subseteq X $
And we define our value function $f(X) := \sum_{i \in U(X)} i - \sum_{j \in L(X)} j$. (I'm also looking for names for this value function)
Our interest is to find a two-way partition $A, B$ of $X$, $A\cup B =X, A\cap B = \emptyset$.
Such that sum of the value from both $A$ $B$ is minimized.
Namely, optimize: $A^*, B^* = \text{argmin}_{A, B} f(A) + f(B), s.t. A,B \subset X, A\cup B =X, A\cap B = \emptyset$.
And So far I've tried the brute force solution by enumerating the power set of $X$ and evaluate all the configurations. Hoping for some faster solutions.
As the brute force solution would have at least $O(2^{n-1})$ complexity. With some effort, I'm able to make a $O(n^6)$ complexity algorithm.
The trick is to find an anchor point to both $A, B$, which is the median.
Since there can maximum be $O(n^2)$ different medians one can get from any subset of $X$.
The unique pairs $(m_A, m_B)$ of medians for $A, B$ are bounded by $O(n^4)$.
Now that the rest of the elements in $X$ not used in the median can be grouped into pairs $(i, j)$, which is $O(n^2)$.
Now we just need two determine, which $(i, j)$ merges with $m_A$ or $m_B$ that maximize the value function.
So in total, there should exist a $O(n^6)$ complexity algorithm.