A Greedy and Distributable Approach to the Lexicographical Bottleneck Assignment Problem with Conditions on Exactness

The Lexicographical Bottleneck Assignment Problem (LexBAP) typically requires centralised computation with quartic complexity. We consider the Sequential Bottleneck Assignment Problem (SeqBAP) and its relationship to the LexBAP. By exploiting structure of the Bottleneck Assignment Problem, we derive an algorithm that solves the SeqBAP with cubic complexity. We analyse conditions for which solutions sets of the LexBAP and the SeqBAP coincide. When these conditions hold, the algorithm solves the LexBAP with computation that can be distributed over a network of agents.