论文标题
在线性分配问题及其应用程序中，与本地重量更新相对于本地重量更新的快速二重更新及其应用
Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application
论文作者
论文摘要
我们考虑在加权两分匹配问题中的动态情况：输入图中的边缘权重反复更新，并要求我们随时保持最佳匹配。一种微不足道的方法是每次更新时从头开始计算最佳匹配。在本文中，我们表明，如果每个更新均在一个顶点周围发生，那么Dijkstra算法的一次执行就足以借助双重解决方案来保持最佳性。作为我们结果的应用，我们提供了更快的嫉妒周期程序的实施，以查找不可分割的项目的无嫉妒分配。我们的算法以$ \ mathrm {o}（mn^2）$时间运行，而原始算法的限制为$ \ mathrm {o}（mn^3）$，其中$ n $和$ m $分别表示代理和物品的数量。
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.
