2019/12/28 by Golin, Mordecai, Sandeep, Sai
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1912.12447
In dynamic flow networks, every vertex starts with items (flow) that need to be shipped to designated sinks. All edges have two associated quantities: length, the amount of time required for a particle to traverse the edge, and capacity, the number of units of flow that can enter the edge in unit time. The goal is move all flow to the sinks. A variation of the problem, modelling evacuation protocols, is to find the sink location(s) that minimize evacuation time, restricting the flow to be CONFLUENT. Solving this problem is is NP-hard on general graphs, and thus research into optimal algorithms has traditionally been restricted to special graphs such as paths, and trees. A specialized version of robust optimization is minmax REGRET, in which the input flows at the vertices are only partially defined by constraints. The goal is to find a sink location that has the minimum regret over all input flows that satisfy the partially defined constraints. Regret for a fully defined input flow and a sink is defined to be the difference between the evacuation time to that sink and the optimal evacuation time. A large recent literature derives polynomial time algorithms for the minmax regret k-sink location problem on paths and trees under the simplifying condition that all edges have the same (uniform) capacity. This paper develops a O(n4 log n) time algorithm for the minmax regret 1-sink problem on paths with general (non-uniform) capacities. To the best of our knowledge, this is the first minmax regret result for dynamic flow problems in any type of graph with general capacities.