An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
This work improves the computational complexity of a fundamental partitioning problem, relevant to operations research and computational geometry.
The paper presents an O(n^2) algorithm for cardinality-constrained diameter partitioning, improving on the previous O(n^2 log n) bound, and provides a matching lower bound. For Euclidean weights in fixed dimension, a subquadratic algorithm is given.
Cardinality-constrained diameter partitioning asks for a partition of $n$ items into two classes of prescribed sizes that minimizes the larger of the two class diameters. We give an $O(n^2)$ algorithm and a matching $Ω(n^2)$ lower bound if we can only query the weight between two elements. The algorithm computes the optimum for every cardinality simultaneously, improving Avis's $O(n^2\log n)$. The reduction is to a bottleneck 2-coloring problem on the maximum spanning tree, solved by a standard tree DP. For a single cardinality with Euclidean weights, we obtain a subquadratic time algorithm in any fixed dimension.