2018/06/11 by Mordecai J. Golin, Golin, Mordecai J., Sai Sandeep +1 · 1 citation
Business, Management and Accounting · Computer Science · #Facility Location and Emergency Management #Mobile Ad Hoc Networks #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1806.03814
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 O(k2 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( max(k2 log2 k,log 2n) k4 n2 log5 n)