A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Mitchell Khoo

doi:10.1109/TAC.2023.3279336

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

2024-02-01

0

OA

AI

DOI：10.1109/TAC.2023.3279336

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Autonomous agents

autonomous systems

distributed algorithms

multi-agent systems

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Abstract

Journal

Organization