A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

• 成果类型: Article
• 署名作者: Khoo, Mitchell; Wood, Tony A.; Manzie, Chris; Shames, Iman
• 署名单位: University of Melbourne; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Australian National University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3279336
• 发表日期: 2024
• 页码: 1210-1217
• 关键词: Autonomous agents; Autonomous systems; Distributed algorithms; Multi-agent systems

摘要

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 the properties of two different methods to search for an augmenting path in a bipartite graph. We evaluate the derived approaches with a simulation-based complexity investigation.