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.