Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations. (June 2023)

• Record Type: Journal Article
• Authors: Dokka, Trivikram; Goerigk, Marc
• Is Part Of: Computers & operations research. Volume 154(2023)
• Publication Date: 2023-06
• Subjects: Combinatorial optimization -- Bottleneck assignment -- Approximation -- Computational complexity; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106213
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: 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.