Minimum-cost load-balancing partitions

DOI10.1007/S00453-007-9125-3MaRDI QIDQ834581zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Paz Carmi, Matthew J. Katz

Publication date 27 August 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9125-3

zbMATH Keywords

approximation algorithmsgeometric optimizationload balancingfatnessadditive-weighted Voronoi diagramfat partitions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Dividing a territory among several vehicles
• Geometric partitioning and robust ad-hoc network design
• The geometry of optimal partitions in location problems
• Finding equitable convex partitions of points in a polygon efficiently
• Finding tailored partitions

Cites work

• scientific article; zbMATH DE number 5506221 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Approximating \(k\)-median with non-uniform capacities
• Geographic quorum system approximations
• Minkowski-type theorems and least-squares clustering
• On the Continuous Fermat-Weber Problem
• On the Fermat-Weber center of a convex object
• Sharp quantum versus classical query complexity separations
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• \(E_{11}\) and M theory

Cited in

(11)

• Shadow prices in territory division
• An approximation algorithm for the continuous \(k\)-medians problem in a convex polygon
• Geometric partitioning and robust ad-hoc network design
• A new approach to the upper bound on the average distance from the Fermat-Weber center of a convex body
• On the upper bound on the average distance from the Fermat-Weber center of a convex body
• A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes
• Balancing graph Voronoi diagrams with one more vertex
• Dividing a territory among several vehicles
• Least-cost partition algorithms
• Constrained clustering via diagrams: a unified theory and its application to electoral district design
• New bounds on the average distance from the Fermat-Weber center of a planar convex body

This page was built for publication: Minimum-cost load-balancing partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834581)