# Partition data into two sets of the same size such that the sum of the average distances is maximized

Say I have a set of strings $$S=\{s_1, s_2, ..., s_N\}$$, and I want to partition $$S$$ into two sets $$S_1$$ and $$S_2$$ equally, i.e., $$||S_1|-|S_2||\leq1$$.

Define the difference of a set as $$Diff(S_k)=\frac{\displaystyle{\sum_{s_i,s_j\in S_k} d(s_i,s_j)}}{\displaystyle{|S_k|\choose 2}}$$

where $$d(s_i,s_j)$$ is a custom distance function that calculates the 'distance' between two strings, satisfying $$d(s_i,s_j)=d(s_j,s_i)$$.

The objective is to find a partition of $$S$$ that maximize $$Diff(S_1)+Diff(S_2)$$, assuming we already have $$d(s_i,s_j)$$ for $$s_i,s_j\in S$$.

Are there any (heuristic) algorithms that I can use to achieve the objective? Or maybe this problem can be generalized to some known problem with loose constraints?

Let us call this problem $$P$$. Assuming we can choose the fucntion $$d$$ freely, this problem is NP-hard. I willl show a proof sketch for the case where $$N$$ is even. This already implies that the problem in general is NP-hard. The proof is a reduction from the balanced cut problem.

Let us define the function $$\operatorname{Diff}'(S_k) = \sum\limits_{s_i, s_j \in S_k} d(s_i, s_j)$$. Let $$P'$$ be the same problem defined over $$\operatorname{Diff}'$$ instead of $$\operatorname{Diff}$$, i.e. the goal is to find a partition that maximizes $$\operatorname{Diff}'(S_1) + \operatorname{Diff}'(S_2)$$. Claerly, for an even value of $$N$$, a solution $$(S_1, S_2)$$ is optimal for $$P$$ if and only if it is optimal for $$P'$$, since $$|S_1| = |S_2|$$, and hence the problems $$P$$ and $$P'$$ are equivalent. We now procede with the problem $$P'$$.

It is quite easy to reduce the balanced cut problem (defined below) to this problem. Intuitively, let us represent the input as a complete weighted graph, where the strings correspond to vertices and the function $$d$$ correspond to the weight of the edges. Our goal is to partition the vertices of this graph into two sets $$(S_1, S_2)$$ in a way that maximizes the total sum of weights of edges in both induced subgraphs $$G[S_1]$$ and $$G[S_2]$$. This is equivalent to minimizing the weight of the cut $$(S_1, S_2)$$, since each edge belongs to either one of the induced subgraphs or is a cut edge. Hence, we aim to find a partition of the vertices into two sets of equal sizes in a way that minimizes the weight of the cut. That is exatly the definition of the weighted balanced cut problem.

Balanced cut problem
Input: An undirected graph $$G$$.
Asked: A partition of $$V(G)$$ into two sets $$(S_1, S_2)$$ of equal sizes,
minimizing the size of the cut $$(S_1, S_2)$$.


This problem is NP-hard, and hence, the weighted version as well. Now it is not hard to reduce the weighted version of this problem to $$P'$$. Given a graph $$G$$ with a weight function $$w$$, we first add all missing edges as edges with weight zero. Now we build a string $$s_v$$ for each vertex $$v$$ and set $$d(s_u, s_v) = w(u, v)$$ for w the given weight function of $$G$$. Cearly this instance of $$P'$$ admits a parition of weight $$k$$ if and only if $$G$$ admits a balanced cut of cost $$W - k$$, where $$W = \sum_{e \in E(G)} w(e)$$.