Probabilistic Analysis of the Planar k-Median Problem

DOI10.1287/moor.5.1.27zbMath0435.90057OpenAlexW2106655555MaRDI QIDQ3875687

Dorit S. Hochbaum, Marshall L. Fisher

Publication date: 1980

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.5.1.27

zbMATH Keywords

asymptotic behaviorprobabilistic analysislocationaggregation heuristicepsilon- optimalitygrowth of optimal valueplanar K-median problemrelationship to problem size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations research and management science (90B99)

Related Items

Maximal paths in random dynamic graphs, Continuous approximation formulas for location problems, Probabilistic analysis of some Euclidean clustering problems, Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations, Average performance of greedy heuristics for the integer knapsack problem., An appraisal of computational complexity for operations researchers, Competitive location in the plane, Heuristic methods and applications: A categorized survey, Worst-case analysis of demand point aggregation for the Euclidean \(p\)-median problem, The \(p\)-median problem in fuzzy environment: proving fuzzy vertex optimality theorem and its application, The simple plant location problem: Survey and synthesis, A comparison of two dual-based procedures for solving the p-median problem, A Probabilistic Analysis of the K-Location Problem, Probabilistic Analysis of Geometric Location Problems