An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon

作者：Carlsson John Gunnar^*; Jia Fan; Li Ying

来源：INFORMS Journal on Computing, 2014, 26(2): 280-289.

DOI：10.1287/ijoc.2013.0564

• approximation algorithms
• geometric algorithms
• continuous location theory

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.

• 出版日期2014