Home > Research > Publications & Outputs > Multi-level bottleneck assignment problems

Associated organisational unit

Electronic data


    Accepted author manuscript, 874 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License


Text available via DOI:

View graph of relations

Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Article number106213
<mark>Journal publication date</mark>30/06/2023
<mark>Journal</mark>Computers and Operations Research
Number of pages12
Publication StatusPublished
Early online date14/03/23
<mark>Original language</mark>English


We study the multi-level bottleneck assignment problem: given a weight matrix, the task is to rearrange entries in each column such that the maximum sum of values in each row is as small as possible. We analyze the complexity of this problem in a generalized setting, where a graph models restrictions how values in columns can be permuted. We present a lower bound on its approximability by giving a non-trivial gap reduction from three-dimensional matching to the multi-level bottleneck assignment problem. We present new integer programming formulations and consider the impact of graph density on problem hardness in numerical experiments.