Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application

Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi +1

We consider a dynamic situation in the weighted bipartite matching problem: edge weights in the input graph are repeatedly updated and we are asked to maintain an optimal matching…