Given a dataset $D$ and a distance measure, I want to split the dataset into two disjoint subsets $X, Y$ of a specified size (say 80% and 20% of the original size), so that the minimum distance of all pairs $(x, y)$ with $x \in X$ and $y \in Y$ is maximized. I found references to max-margin clustering without the size constraint, however my feeling is that the constraint should make the problem easier - does it? Is there some straightforward way to solve this problem?
A bit vague answer, but I'll give it a chance. I always felt that the size constraint is the central idea behind this method -- without is seems just to converge to other approaches, effectively to 2-means and ideologically to unsupervised SVM. The previous rather invalidates this idea, the latter way is more intriguing while you may hope to save some pain using SVM optimization framework and kernel tricks.