# Efficient solutions for weight-balanced partitioning problems

**Authors:** Steffen Borgwardt, Shmuel Onn  
**arXiv:** [1503.06877](https://arxiv.org/abs/1503.06877)  
**Date:** 2015-03-24  
**Summary page:** https://www.summarizepaper.com/en/paper/1503.06877v3/

## Key points

- The paper presents a polynomial-time solvability proof for clustering problems with balancing constraints
- The weights of the data points are determined by different features
- Clusters must adhere to specified lower and upper bounds on total weight with respect to each feature
- Weight-contribution of a vector can depend on the assigned cluster
- Motivation for studying these problems comes from land consolidation
- The authors propose a framework that maximizes an objective function, which is convex in utility of items within clusters
- The clustering model can be solved in polynomial time for fixed dimensions and number of clusters
- Efficient solvability result holds true for weight-balancing restrictions defined using vectors from a fixed, finite domain
- A new model and algorithm specifically designed for land consolidation is presented
- Research provides insights into solving clustering problems with balancing constraints efficiently

## Summary

The paper titled "Efficient solutions for weight-balanced partitioning problems" by Steffen Borgwardt and Shmuel Onn presents a polynomial-time solvability proof for a large class of clustering problems. These problems involve partitioning a weighted set of items into clusters based on balancing constraints. The weights of the data points are determined by different features, and the clusters must adhere to specified lower and upper bounds on the total weight of their points with respect to each feature. One key aspect of this clustering problem is that the weight-contribution of a vector to a cluster can depend on the specific cluster it is assigned to. The motivation for studying these types of clustering problems comes from their application in land consolidation, where achieving balance in terms of weight distribution is crucial. The authors propose a framework that maximizes an objective function, which is convex in the summed-up utility of the items within each cluster. Despite the inherent hardness associated with convex maximization and related problems, they demonstrate that their clustering model can be solved in polynomial time when considering fixed dimensions and number of clusters. Importantly, this efficient solvability result holds true if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. The paper concludes by presenting a new model and algorithm specifically designed for land consolidation. In summary, this research provides valuable insights into solving clustering problems with balancing constraints efficiently. The findings have practical implications in various domains beyond land consolidation, where similar weight-balanced partitioning challenges arise.