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

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

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2023-06, Vol.154, p.106213, Article 106213
Main Authors: Dokka, Trivikram, Goerigk, Marc
Format: Article
Language:English
Subjects:
Approximation
Bottleneck assignment
Combinatorial optimization
Computational complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. •We study the complexity of multi-level bottleneck assignment (MBAP) problems.•The MBAP is known to be NP-hard.•We show a lower bound on the approximability depending on the number of layers.•In our proof the underlying graph is sparse.•A computational analysis explores the impact of sparsity on problem difficulty.
ISSN:0305-0548
1873-765X
DOI:10.1016/j.cor.2023.106213