Constrained Minimum‐k‐Star Clustering and its application to the consolidation of farmland

The present paper introduces and studies a new combinatorial clustering model for the consolidation of farmland. While the general problem turns out to be NP‐hard even in quite restricted cases, the Size‐restricted Minimum‐k‐Star Group Partition problem is solvable in polynomial time. Based on this tractability result, we derive a general approximation algorithm which, as the mathematical analysis and economic evaluation shows, performs well in theory and practice.