  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(n^4 \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.
