Journal article

Exploiting Structure in the Bottleneck Assignment Problem

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



An assignment problem arises when there exists a set of tasks that must be allocated to a set of agents. The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment. In particular, we discuss merging the assignments from two separate BAPs and use the solution of the subproblems to bound the solution of the combined problem. We also provide conditions for cases where the solution of the subproblems produces an exact solution to the BAP over the co..

View full abstract


Awarded by Defence Science and Technology Group

Funding Acknowledgements

The research is funded by Defence Science and Technology Group through research agreements MyIP: 7558 and MyIP: 7562.