Minmax-Regret k-Sink Location on a Dynamic Tree Network with Uniform Capacities
share
A dynamic flow network G with uniform capacity c is a graph in which at most c units of flow can enter an edge in one time unit. If flow enters a vertex faster than it can leave, congestion occurs. The evacuation problem is to evacuate all flow to sinks assuming that all flow is confluent, i.e., all flow passing through a particular vertex must follow the same exit edge. The k-sink location problem is to place k-sinks so as to minimize this evacuation time. Although the k-sink location problem is NP-Hard on a general graph it can be solved in Õ(k^2 n) time on trees. The concept of minmax-regret arises from robust optimization. For each source, a range of possible flow values is provided and any scenario with flow values in those ranges might occur. The goal is to find a sink placement that minimizes, over all possible scenarios, the difference between the evacuation time to those sinks and the minimal evacuation time of that scenario. The Minmax-Regret k-Sink Location on a Dynamic Path Networks with uniform capacities is polynomial solvable in n and k. Similarly, the Minmax-Regret k-center problem on trees is polynomial solvable in n and k. Prior to this work, polynomial time solutions to the Minmax-Regret k-Sink Location on Dynamic Tree Networks with uniform capacities were only known for k=1. This paper solves this problem, for general k, in time O( (k^2, ^2n) k^2 n^2 ^5 n).
READ FULL TEXT