k-center in a large graph (road-network)

Question

I'm currently looking for a way to solve the k-center problem on a large, sparse graph. The data comes from openstreetmap and I want to place k pizza-delivery-branches in the city in such way as the distance to any node in the graph from a branch is minimized.

---

Example: Where should I place 3 pizza-delivery-branches to cover the city the best?

---

Problem: The graph contains approximately 50,000 to 250,000 nodes (data from openstreetmap).

Simplifaction: The solution doesn't have to be perfect. An approximation will suffice. k will be smaller than 20. Runtimes of several hours are ok.

I can't wait to hear from your ideas how to solve the problem on such a large real-world-graph (road-network).

Answer 1

The following greedy algorithm is a 2-approximation for instances where the travel time of each road is the same in both directions. (Ignoring one-way streets shouldn't distort travel times too much.)

Choose the first center arbitrarily. For each subsequent center, choose the vertex farthest from the existing centers. Using the multiple-source extension of Dijkstra's algorithm (initialize the priority queue to contain all of the existing centers with distance 0), a good implementation running on contemporary hardware with parameters n=250,000 and k=20 I reckon should take at most a second or two.