1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.