A clustering problem with 0 or 1 distances for minimizing the summation of distances

I have a clustering problem with $$\{0,1\}$$ distances between a set of nodes, which can be stated as follows:

Given: Finite set $$\mathbb{X}$$, a distance $$d(x, y) \in \{0,1\}$$ for each pair $$(x, y) \in \mathbb{X}$$, and positive integers $$S$$ and $$H$$.

QUESTION: Is there a partition of $$\mathbb{X}$$ into disjoint sets $$\mathbb{X}_1, \mathbb{X}_2, \dots, \mathbb{X}_S$$ to minimize $$\sum_{s=1}^S \sum_{x,y \in \mathbb{X}_s} d(x,y)$$ where $$|\mathbb{X}_s| \leq H$$?

Is there a specific name for such a clustering problem so that I can find the complexity proof of it?

1 Answer

This is a variant of the minimum $$k$$-cut problem. The node set is $$\mathbb{X}$$, the edge weights are $$1-d(x,y)$$, and $$k=S$$.

Also related to the wedding planner problem, where $$\mathbb{X}$$ is the set of guests, $$S$$ is the number of tables, and $$H$$ is the maximum number of guests per table. Here, $$d(x,y)$$ measures whether $$x$$ and $$y$$ dislike each other. See https://blogs.sas.com/content/operations/2014/11/10/do-you-have-an-uncle-louie-optimal-wedding-seat-assignments/

• Thank you, professor, for you answer. Jan 13 at 14:21
• Since it is a SAS employee linking to a SAS blog post....Disclosure: This excellent answer provided by the Senior R&D Manager, SAS Institute Inc. Jan 13 at 14:27