Distributed Algorithm for Solving the Bottleneck Assignment Problem

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

doi:10.1109/CDC40024.2019.9028897

Distributed Algorithm for Solving the Bottleneck Assignment Problem

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

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 language	English
Title of host publication	2019 IEEE 58th Conference on Decision and Control, CDC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1850-1855
Number of pages	6
ISBN (Electronic)	9781728113982
DOIs	https://doi.org/10.1109/CDC40024.2019.9028897
Publication status	Published - Dec 2019
Externally published	Yes
Event	58th IEEE Conference on Decision and Control, CDC 2019 - Nice, France Duration: 11 Dec 2019 → 13 Dec 2019

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2019-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	58th IEEE Conference on Decision and Control, CDC 2019
Country/Territory	France
City	Nice
Period	11/12/19 → 13/12/19

Access to Document

10.1109/CDC40024.2019.9028897

Cite this

Khoo, M., Wood, T. A., Manzie, C., & Shames, I. (2019). Distributed Algorithm for Solving the Bottleneck Assignment Problem. In 2019 IEEE 58th Conference on Decision and Control, CDC 2019 (pp. 1850-1855). Article 9028897 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC40024.2019.9028897

@inproceedings{b61890147fce48bd8f7c13c23b9a7f99,

title = "Distributed Algorithm for Solving the Bottleneck Assignment Problem",

abstract = "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.",

author = "Mitchell Khoo and Wood, {Tony A.} and Chris Manzie and Iman Shames",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 58th IEEE Conference on Decision and Control, CDC 2019 ; Conference date: 11-12-2019 Through 13-12-2019",

year = "2019",

month = dec,

doi = "10.1109/CDC40024.2019.9028897",

language = "English",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1850--1855",

booktitle = "2019 IEEE 58th Conference on Decision and Control, CDC 2019",

address = "United States",

}

Khoo, M, Wood, TA, Manzie, C & Shames, I 2019, Distributed Algorithm for Solving the Bottleneck Assignment Problem. in 2019 IEEE 58th Conference on Decision and Control, CDC 2019., 9028897, Proceedings of the IEEE Conference on Decision and Control, vol. 2019-December, Institute of Electrical and Electronics Engineers Inc., pp. 1850-1855, 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, 11/12/19. https://doi.org/10.1109/CDC40024.2019.9028897

Distributed Algorithm for Solving the Bottleneck Assignment Problem. / Khoo, Mitchell; Wood, Tony A.; Manzie, Chris et al.
2019 IEEE 58th Conference on Decision and Control, CDC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1850-1855 9028897 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Distributed Algorithm for Solving the Bottleneck Assignment Problem

AU - Khoo, Mitchell

AU - Wood, Tony A.

AU - Manzie, Chris

AU - Shames, Iman

PY - 2019/12

Y1 - 2019/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85082453934&partnerID=8YFLogxK

U2 - 10.1109/CDC40024.2019.9028897

DO - 10.1109/CDC40024.2019.9028897

M3 - Conference contribution

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 1850

EP - 1855

BT - 2019 IEEE 58th Conference on Decision and Control, CDC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 58th IEEE Conference on Decision and Control, CDC 2019

Y2 - 11 December 2019 through 13 December 2019

ER -

Distributed Algorithm for Solving the Bottleneck Assignment Problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this