  Optimal transport is a fundamental topic that has attracted a great amount of
attention from the optimization community in the past decades. In this paper,
we consider an interesting discrete dynamic optimal transport problem: can we
efficiently update the optimal transport plan when the weights or the locations
of the data points change? This problem is naturally motivated by several
applications in machine learning. For example, we often need to compute the
optimal transport cost between two different data sets; if some changes happen
to a few data points, should we re-compute the high complexity cost function or
update the cost by some efficient dynamic data structure? We are aware that
several dynamic maximum flow algorithms have been proposed before, however, the
research on dynamic minimum cost flow problem is still quite limited, to the
best of our knowledge. We propose a novel 2D Skip Orthogonal List together with
some dynamic tree techniques. Although our algorithm is based on the
conventional simplex method, it can efficiently find the variable to pivot
within expected $O(1)$ time, and complete each pivoting operation within
expected $O(|V|)$ time where $V$ is the set of all supply and demand nodes.
Since dynamic modifications typically do not introduce significant changes, our
algorithm requires only a few simplex iterations in practice. So our algorithm
is more efficient than re-computing the optimal transport cost that needs at
least one traversal over all $|E| = O(|V|^2)$ variables, where $|E|$ denotes
the number of edges in the network. Our experiments demonstrate that our
algorithm significantly outperforms existing algorithms in the dynamic
scenarios.
