Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application
| Autor: | Morita, Kohei, Shiroshita, Shinya, Yamaguchi, Yutaro, Yokoi, Yu |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 at any moment. A trivial approach is to compute an optimal matching from scratch each time an update occurs. In this paper, we show that if each update occurs locally around a single vertex, then a single execution of Dijkstra's algorithm is sufficient to preserve optimality with the aid of a dual solution. As an application of our result, we provide a faster implementation of the envy-cycle procedure for finding an envy-free allocation of indivisible items. 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. Comment: Accepted by Information Processing Letters; 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|