Maintaining Optimality in Assignment Problem against Weight Updates around Vertices

We consider a dynamic situation in the weighted bipartite matching problem in which edge weights are repeatedly updated and each update occurs around a single vertex. Our objective is to maintain an optimal matching at any moment. A trivial approach is to compute an optimal matching from scratch each time an update occurs, but this seems inefficient. In this paper, we show that, if we simultaneously maintain a dual solution, then it suffices to perform Dijkstra's algorithm only once per update. As an application of our result, we provide a faster implementation of the envy-cycle procedure for finding an envy-free allocation of indivisible goods. Our algorithm runs in $\mathrm{O}(mn^2)$ time, while the known bound of the original one is $\mathrm{O}(mn^3)$, where $n$ and $m$ denote the numbers of agents and items, respectively.