  We prove polynomial-time solvability of a large class of clustering problems
where a weighted set of items has to be partitioned into clusters with respect
to some balancing constraints. The data points are weighted with respect to
different features and the clusters adhere to given lower and upper bounds on
the total weight of their points with respect to each of these features.
Further the weight-contribution of a vector to a cluster can depend on the
cluster it is assigned to. Our interest in these types of clustering problems
is motivated by an application in land consolidation where the ability to
perform this kind of balancing is crucial.
  Our framework maximizes an objective function that is convex in the summed-up
utility of the items in each cluster. Despite hardness of convex maximization
and many related problems, for fixed dimension and number of clusters, we are
able to show that our clustering model is solvable in time polynomial in the
number of items if the weight-balancing restrictions are defined using vectors
from a fixed, finite domain. We conclude our discussion with a new, efficient
model and algorithm for land consolidation.
