An Approximation Algorithm for the Continuousk-Medians Problem in a Convex Polygon
John Gunnar Carlsson, Fan Jia, Ying Li
INFORMS Journal on Computing · 2014 · Volume 26 · Issue 2
Abstract
We give a fast and simple factor 2.74 approximation algorithm for the problem of choosing the k medians of the continuum of demand points defined by a convex polygon C . Our algorithm first surrounds the input region with a bounding box, then subdivides the bounding box into subregions with equal area. Simulation results on the convex hulls of the 50 states in the United States show that the practical performance of our algorithm is within 10% of the optimal solution in the vast majority of cases.
Keywords
approximation algorithms, geometric algorithms, continuous location theory
Enable JavaScript for citation tools and additional paper interactions.