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).