Efficient solutions for weight-balanced partitioning problems
Authors: Steffen Borgwardt, Shmuel Onn
Abstract
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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Towards balanced clustering - part 1 (preliminaries)Mark Sh. Levin · 2017 · arXiv.org · preprint, not peer reviewed · cited 8 times · Not summarized yet
Abstract
The article contains a preliminary glance at balanced clustering problems. Basic balanced structures and combinatorial balanced problems are briefly described. A special attention is targeted to various balance/unbalance indices (including some new versions of the indices): by cluster cardinality, by cluster weights, by inter-cluster edge/arc weights, by cluster element structure (for element multi-type clustering). Further, versions of optimization clustering problems are suggested (including multicriteria problem formulations). Illustrative numerical examples describe calculation of balance indices and element multi-type balance clustering problems (including example for design of student …
-
Sparse Subspace Clustering: Algorithm, Theory, and ApplicationsEhsan Elhamifar, Rene Vidal · 2012 · Computer Vision and Pattern Recognition · cited 2,503 times · Not summarized yet
Abstract
In many real-world problems, we are dealing with collections of high-dimensional data, such as images, videos, text and web documents, DNA microarray data, and more. Often, high-dimensional data lie close to low-dimensional structures corresponding to several classes or categories of the data. In this paper, we propose and study an algorithm, called Sparse Subspace Clustering, to cluster data points that lie in a union of low-dimensional subspaces. The key idea is that, among infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points that come from the same subspace. This motivates solving a sparse optimiza…
-
Constrained Minimum-k-Star Clustering and its application to the consolidation of farmlandSteffen Borgwardt, A. Brieden, P. Gritzmann · 2011 · Operational Research · cited 25 times · Not summarized yet
-
On Optimal Weighted Balanced Clusterings: Gravity Bodies and Power DiagramsA. Brieden, P. Gritzmann · 2012 · SIAM Journal on Discrete Mathematics · cited 40 times · Not summarized yet
-
Constrained Clustering: Advances in Algorithms, Theory, and ApplicationsSugato Basu, I. Davidson, K. Wagstaff · 2008 · cited 548 times · Not summarized yet
-
A decision-tree framework to select optimal box-sizes for product shipmentsKarthik S. Gurumoorthy, Abhiraj Hinge · 2022 · Machine Learning · cited 1 time · AI summary available
Abstract
In package-handling facilities, boxes of varying sizes are used to ship products. Improperly sized boxes with box dimensions much larger than the product dimensions create wastage and unduly increase the shipping costs. Since it is infeasible to make unique, tailor-made boxes for each of the $N$ products, the fundamental question that confronts e-commerce companies is: How many $K << N$ cuboidal boxes need to manufactured and what should be their dimensions? In this paper, we propose a solution for the single-count shipment containing one product per box in two steps: (i) reduce it to a clustering problem in the $3$ dimensional space of length, width and height where each cluster corresponds…
-
Optimally solving the joint order batching and picker routing problemCristiano Arbex Valle, John E Beasley, Alexandre Salles da Cunha · 2017 · Optimization and Control · cited 128 times · Not summarized yet
Abstract
In this work we investigate the problem of order batching and picker routing in storage areas. These are labour and capital intensive problems, often responsible for a substantial share of warehouse operating costs. In particular, we consider the case of online grocery shopping in which orders may be composed of dozens of items. We present a formulation for the problem based on an exponential number of connectivity constraints and we introduce a significant number of valid inequalities based on the standard layout of warehouses, composed of parallel aisles and two or more cross-aisles. The proposed inequalities are highly effective and greatly improve computational results. Instances involvi…
-
Location and portfolio selection problems: A unified frameworkJusto Puerto, Moises Rodríguez-Madrena, Andrea Scozzari · 2019 · Portfolio Management · preprint, not peer reviewed · AI summary available
Abstract
Given a set of assets and an investment capital, the classical portfolio selection problem consists in determining the amount of capital to be invested in each asset in order to build the most profitable portfolio. The portfolio optimization problem is naturally modeled as a mean-risk bi-criteria optimization problem where the mean rate of return of the portfolio must be maximized whereas a given risk measure must be minimized. Several mathematical programming models and techniques have been presented in the literature in order to efficiently solve the portfolio problem. A relatively recent promising line of research is to exploit clustering information of an assets network in order to devel…
Prior work it builds on
-
On Clustering Bodies: Geometry and Polyhedral ApproximationA. Brieden, P. Gritzmann · 2010 · Discrete & Computational Geometry · cited 18 times · Not summarized yet
-
Geometric Clustering for the Consolidation of Farmland and WoodlandSteffen Borgwardt, A. Brieden, P. Gritzmann · 2014 · The Mathematical Intelligencer · cited 36 times · Not summarized yet
-
Convex integer maximization via Graver basesJ. De Loera, R. Hemmecke, S. Onn et al. · 2006 · Journal of Pure and Applied Algebra · cited 38 times · Not summarized yet
Abstract
We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on Rd and w1x,…,wdx are linear forms on Rn, max{c(w1x,…,wdx):Ax=b,x∈Nn}. This method works for arbitrary input data A,b,d,w1,…,wd,c. Moreover, for fixed d and several important classes of programs in variable dimension, we prove that our algorithm runs in polynomial time. As a consequence, we obtain polynomial time algorithms for various types of multi-way transportation problems, packing problems, and partitioning problems in variable dimension.
-
Clustering with Size ConstraintsF. Höppner, F. Klawonn · 2008 · Computational Intelligence Paradigms · cited 49 times · Not summarized yet
-
Algebraic and Geometric Ideas in the Theory of Discrete OptimizationJ. De Loera, R. Hemmecke, M. Köppe · 2012 · MOS-SIAM Series on Optimization · cited 178 times · Not summarized yet
Papers that cite it
-
Circuits in extended formulationsSteffen Borgwardt, Matthias Brugger · 2022 · Discrete Optimization · cited 1 time · Not summarized yet
Abstract
Circuits and extended formulations are classical concepts in linear programming theory. The circuits of a polyhedron are the elementary difference vectors between feasible points and include all edge directions. We study the connection between the circuits of a polyhedron $P$ and those of an extended formulation of $P$, i.e., a description of a polyhedron $Q$ that linearly projects onto $P$. It is well known that the edge directions of $P$ are images of edge directions of $Q$. We show that this `inheritance' under taking projections does not extend to the set of circuits. We provide counterexamples with a provably minimal number of facets, vertices, and extreme rays, including relevant polyt…
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 4 November 2026.