AI summary · arXiv: 1503.06877v3 · math.OC

Efficient solutions for weight-balanced partitioning problems

Steffen Borgwardt, Shmuel Onn
Original paper · DOI 10.1016/j.disopt.2016.06.001 Submitted to arXiv on 24 Mar. 2015 Published in Discrete Optimization (August 2016) License: NONEXCLUSIVE-DISTRIB 1.0

How to read this summary? Illustrated guide

The essentials

  • 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

Key points written by AI: they may contain errors, check them against the paper.

AI-generated keywords: Efficient solutions Weight-balanced partitioning problems Polynomial-time solvability proof Clustering problems Land consolidation

Read further

  • Comprehensive Summary
  • Layman's Summary
  • Blog article
  • Original abstract
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.

Was this synthesis useful?

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Figures and plots

Ask about a figure by number or use its question button to request visual analysis. Up to two figures and four image panels per question. Values read from plots are approximate; check the original data.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today
Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero Zotero guide
Citation alerts 2 papers already cite it: be emailed each new one. Citation alerts guide
Who works on it?

Among the 24 papers around this one, the name that comes back most: A. Brieden (5 papers)

6 more people sign several of them. The full map adds their institutions and approaches, from the papers of the last years.

Continue with Google Create a free account: your first map is free
Weekly letter The latest letter of its field, "Mathematics and statistics this week" of 16 November 2026: Mathematics and statistics this week: Arithmetic, crystals and the limits of shape · Receive one by email for free

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

  1. Close Cites this paper
    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 …

  2. Close
    Sparse Subspace Clustering: Algorithm, Theory, and Applications
    Ehsan 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…

  3. Close* Cited by this paper Used in depth by this paper A method it uses
    Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland
    Steffen Borgwardt, A. Brieden, P. Gritzmann · 2011 · Operational Research · cited 25 times · Not summarized yet
  4. Related* Cited by this paper A method it uses
    On Optimal Weighted Balanced Clusterings: Gravity Bodies and Power Diagrams
    A. Brieden, P. Gritzmann · 2012 · SIAM Journal on Discrete Mathematics · cited 40 times · Not summarized yet
  5. Related* Cited by this paper
    Constrained Clustering: Advances in Algorithms, Theory, and Applications
    Sugato Basu, I. Davidson, K. Wagstaff · 2008 · cited 548 times · Not summarized yet
  6. Related
    A decision-tree framework to select optimal box-sizes for product shipments
    Karthik 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…

  7. Related
    Optimally solving the joint order batching and picker routing problem
    Cristiano 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…

  8. Related
    Location and portfolio selection problems: A unified framework
    Justo 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

  1. Related* A method it uses
    On Clustering Bodies: Geometry and Polyhedral Approximation
    A. Brieden, P. Gritzmann · 2010 · Discrete & Computational Geometry · cited 18 times · Not summarized yet
  2. Related*
    Geometric Clustering for the Consolidation of Farmland and Woodland
    Steffen Borgwardt, A. Brieden, P. Gritzmann · 2014 · The Mathematical Intelligencer · cited 36 times · Not summarized yet
  3. Related
    Convex integer maximization via Graver bases
    J. 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.

  4. Related*
    Clustering with Size Constraints
    F. Höppner, F. Klawonn · 2008 · Computational Intelligence Paradigms · cited 49 times · Not summarized yet
  5. Related*
    Algebraic and Geometric Ideas in the Theory of Discrete Optimization
    J. De Loera, R. Hemmecke, M. Köppe · 2012 · MOS-SIAM Series on Optimization · cited 178 times · Not summarized yet

Papers that cite it

  1. Related
    Circuits in extended formulations
    Steffen 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…

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.

The illustrated guide to the papers around a paper

The previous summary was created more than a year ago and can be re-run (if necessary) by clicking on the Run button below.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.