A sub-quadratic algorithm for the minsum one sink location problem on balanced binary tree networks

We focus on the problem of locating one sink on balanced binary tree networks with uniform edge capacities, all while minimizing the total evacuation time for all evacuees (minsum criterion). The challenge with sink location problems is modelling congestion, which determines evacuation time during a major disaster. Sub-quadratic algorithms exist to locate a single sink that minimizes the min-sum objective for path and cycle networks. Designing a sub-quadratic algorithm to locate a single sink on a tree network has been an open problem for approximately ten years. Our algorithm has a time complexity of O(n log2 n), where n is the number of vertices in the network. We achieve this result by introducing two new ideas. First, we define the concept of modified clusters, which captures the change in the congestion information computed during the pre-processing phase, to account for new evacuation paths. Second, we devise a simple and efficient method to determine the costs associated with every potential sink, using the partial information gathered from the modified clusters that are accessible at several network nodes.