Distributed Algorithm for Solving the Bottleneck Assignment Problem

Mitchell Khoo, Tony A. Wood, Chris Manzie, Iman Shames

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)


Assignment problems are found in multiagent systems, where there is a need to allocate multiple tasks to agents. The bottleneck assignment problem (BAP) is an assignment problem where the objective is to minimise the worst individual cost in the assignment. Distributed algorithms for assignments with other objectives have been proposed, yet to date no distributed algorithm for the BAP exists. This paper addresses this gap; we develop a novel distributed algorithm that solves the BAP optimally. The algorithm does not require a centralised decision-maker having access to all information from each agent, which is an advantage over existing algorithms for solving the BAP. We use numerical simulations to compare the optimality of the proposed algorithm against a greedy assignment-finding algorithm.

Original languageEnglish
Title of host publication2019 IEEE 58th Conference on Decision and Control, CDC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781728113982
Publication statusPublished - Dec 2019
Externally publishedYes
Event58th IEEE Conference on Decision and Control, CDC 2019 - Nice, France
Duration: 11 Dec 201913 Dec 2019

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Conference58th IEEE Conference on Decision and Control, CDC 2019


Dive into the research topics of 'Distributed Algorithm for Solving the Bottleneck Assignment Problem'. Together they form a unique fingerprint.

Cite this