Greedy algorithms for the single-demand facility location problem

In this note, we give greedy approximation algorithms for the single-demand facility location problem inspired by the greedy algorithms for the min-knapsack problem originally given by Gens and Levner (1979) and later analyzed by Csirik et al. (1991). The simplest algorithm is a 2-approximation algorithm running in O(nlogn) time; in general, we give a k+1k-approximation algorithm running in O(nklogn) time.