k-center

Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it.

Time complexity O(k (V+E) log V), gograph function path.KCenter.

How it works

Where should a company open k warehouses so that no address is a long drive from all of them? Trying every choice is far too slow on a city, so path.KCenter chooses them farthest first: it opens the first warehouse, then keeps opening the next one at the address farthest from every warehouse so far. Each new warehouse needs a search only over the addresses it gets closer to, and k rounds cost O(k (V+E) log V).

When every road works both ways in the same time, the longest drive this leaves is never more than twice the best any k warehouses can do. With one-way streets the drives aren't symmetric, and that factor of two isn't guaranteed.

The second warehouse often lands at the edge of the map. The method shrinks the worst drive, so it serves the most remote address first. That is the difference from k-median, which minimizes the average drive and puts warehouses nearer the busy middle.

Warehouses that are already open can be passed as fixed centers. They count toward k and open first, in the order given. Without them, the first center is the first vertex added to the graph. Which one opens first changes the rest.

Rasht streets

The main streets of Rasht in northern Iran, from OpenStreetMap, with the Gohar Roud and Zar Joub rivers running through the city. Each intersection is named after its streets in English, one-way streets go one way, and each edge is the minutes to drive it at the speed limit, or at 22 to 40 km/h by road type where the map has no limit.

A directed, weighted graph with 298 vertices and 568 edges.

Map data © OpenStreetMap contributors.

With one warehouse at Gomnam Underpass & Gomnam Sq, where should three more open so that the longest drive to any intersection is as short as it can be made?

Open warehouses at Gomnam Underpass & Gomnam Sq, Modarres Hwy near Navy Sq (S), Atefi St & Takhti St and Gholipur Blvd near Gholipur Frontage Rd (1), in that order. The longest drive is 5.78.

Step by step

No warehouse is open yet, so every drive time starts at ∞.
Open warehouse 1 at Gomnam Underpass & Gomnam Sq, which is given. A search from it gives every place it reaches a drive time. The search goes on to Beheshti Blvd & Gomnam Underpass, Beheshti Frontage Rd near Gomnam Underpass, Gomnam Blvd & Gomnam Frontage Rd, Gomnam Bridge & Eftekhari Frontage Rd, Gomnam Sq near Gomnam Underpass (N), Gomnam Sq near Gomnam Underpass (S) and Taleghani Frontage Rd near Gomnam Bridge (S).
Take Gomnam Sq near Gomnam Underpass (N) from the queue. Warehouse 1 reaches it in 0.06, and nothing reaches it sooner. It has no neighbor left to check.
Take Gomnam Sq near Gomnam Underpass (S) from the queue. Warehouse 1 reaches it in 0.08, and nothing reaches it sooner. It has no neighbor left to check.
Take Taleghani Frontage Rd near Gomnam Bridge (S) from the queue. Warehouse 1 reaches it in 0.12, and nothing reaches it sooner. The search goes on to Gomnam Bridge & Taleghani Ave.
Take Beheshti Frontage Rd near Gomnam Underpass from the queue. Warehouse 1 reaches it in 0.13, and nothing reaches it sooner. Beheshti Blvd & Gomnam Underpass already has a drive at least as quick.

538 more steps lead to the last one:

Warehouse 4's search is done. 42 places moved to it. 4 warehouses are open. The farthest place from every warehouse is Shohadaye Salamat St near Razi Sq (E), 5.78 from warehouse 1, so the longest drive is 5.78. There are 322,014,330 ways to choose 4 of the 298 places, too many to try. Some roads here are one way, so the factor of two isn't guaranteed.

Use it in Go

centers, longest, err := path.KCenter(g, 4, "Gomnam Underpass & Gomnam Sq")
if err != nil {
	return err
}
for _, v := range centers {
	fmt.Println(v.Label())
}
fmt.Println(longest)

Example graphs

New York streets, 295 vertices and 669 edges
London streets, 274 vertices and 598 edges
San Francisco streets, 248 vertices and 548 edges
Rasht streets, 298 vertices and 568 edges
School run, 6 vertices and 13 edges
Downtown grid, 20 vertices and 60 edges
One-way city, 45 vertices and 88 edges
Metro region, 100 vertices and 346 edges