Proportional Clustering: Verification and Optimal Selection

We study the problem of proportional clustering. When clustering is used to select representatives, keeping each point close to a center does not ensure that large groups receive a proportional share of the centers. We ask when this proportionality can be checked exactly and when it can be imposed while still optimizing the clustering objective exactly. We consider metric proportional justified representation (mPJR) and its stronger variant mPJR$+$. In arbitrary metrics, we reduce exact mPJR$+$ verification to maximum flow; the same test computes the largest number of missing centers and, through a finite search, the smallest dilation of representation distances under which mPJR$+$ holds. On the real line, we show that proportionality and clustering loss share an interval structure. As a result, a single minimum-cost flow finds an optimal weighted discrete $k$-median or $k$-means selection subject to mPJR, and also makes an existing selection proportional with the fewest replacements. In contrast, verifying mPJR is already coNP-complete in four-dimensional Euclidean space. With exact optimization, the cost of proportionality relative to the unconstrained optimum can still be arbitrarily large, even on the line. Experiments on synthetic populations and model confidence scores separate the cost of mPJR from the additional cost of mPJR$+$ and from the cost of retaining existing centers.