Quick k-Median, k-Center, and Facility Location for Sparse Graphs

We present Õ(m) time and space constant factor approximation algorithms for the k-median, k-center, and facility location problems with assignment costs being shortest path distances in a weighted undirected graph with n vertices and m edges. For all of these location problems, Õ(n²) time and space algorithms were already known, but here we are addressing large sparse graphs. An application could be placement of content distributing servers on the Internet. The Internet is large and changes so frequently that an Õ(n²) time solution would likely be outdated long before completion.