New for: D3
k of these n cities so that the total distance of the cities to the
nearest service-center is minimised. The talk will discuss a simple
swap heursitic for this problem and show that this heursitic leads to
a 5-approximation algorithm. A generalization of this heursitic leads
to improved performance guarantees approaching 3.
The talk will assume no background knowledge.