Maximizing Network Coverage Under the Presence of Time Constraint by Injecting Most Effective k-Links.

We focus on a class of link injection problem of spatial network, i.e., finding best places to construct k new roads that save as many people as possible in a time-critical emergency situation. We quantify the network performance by node coverage under the presence of time constraint and propose an efficient algorithm that maximizes the marginal gain by use of lazy evaluation making the best of time constraint. We apply our algorithm to three problem scenarios (disaster evacuation, ambulance call, fire engine dispatch) using real-world road network and geographical information of actual facilities and demonstrate that 1) use of lazy evaluation can achieve nearly two orders of magnitude reduction of computation time compared with the straightforward approach and 2) the location of new roads is intuitively explainable and reasonable.