论文标题
瓶颈分配问题的分布式增强路径方法
A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem
论文作者
论文摘要
我们开发了一种算法来解决瓶颈分配问题（BAP），该问题可容纳在代理网络上分布计算。这包括探索如何分布算法的每个组件，尤其是一个组件，即搜索增强路径的功能。增强路径是大多数BAP算法中使用的常见工具，并对这种分布式方法提出了一个特殊的挑战。鉴于这种意义，我们比较了两种不同的方法来搜索两分图中的增强路径。我们还利用增强路径的属性来形式化条件，可以使用来自代理集和任务集的子集的解决方案，以用全套的代理和任务来解决BAP。最后，我们评估并比较了衍生方法与数值分析。
We develop an algorithm to solve the Bottleneck Assignment Problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one component in particular, i.e., the function to search for an augmenting path. An augmenting path is a common tool used in most BAP algorithms and poses a particular challenge for this distributed approach. Given this significance, we compare two different methods to search for an augmenting path in a bipartite graph. We also exploit properties of the augmenting paths to formalise conditions for which the solution from subsets of the sets of agents and tasks can be used to solve the BAP with the full sets of agents and tasks. In the end, we evaluate and compare the derived approaches with a numerical analysis.
