A Combinatorial Optimization Approach to Constrained Clustering
Steffen Borgwardt · 2010
Motivated by an application in the consolidation of farmland, we study two polytopes tied to the clustering of a geometric point set into clusters of prescribed sizes. First, we characterize the vertices of the 'gravity polytope' as belonging to clusterings that allow a 'full cell decomposition' of the underlying space such that each cluster lies in its own cell. Hereby we obtain an alternative characterization of power diagrams. We show that a vertex of the gravity polytope (and a corresponding full cell decomposition) can be computed by solving a linear program over the 'partition polytope'. This leads to efficient data classification and prediction algorithms. We then study the edge-structure of the two polytopes and derive a tight upper bound on the combinatorial diameter of the partition polytope. Finally, inspired by our polytopal studies, we devise a combinatorial optimization model for our real-world problem.