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

Research

Associated organisational unit

Electronic data

  • MBAC_CAOR23

    Accepted author manuscript, 874 KB, PDF document

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

Links

Text available via DOI:

Keywords

View graph of relations

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

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations. / Dokka, Trivikram; Goerigk, Marc.
In: Computers and Operations Research, Vol. 154, 106213, 30.06.2023.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Dokka, T & Goerigk, M 2023, 'Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations', Computers and Operations Research, vol. 154, 106213. https://doi.org/10.1016/j.cor.2023.106213

APA

Dokka, T., & Goerigk, M. (2023). Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations. Computers and Operations Research, 154, Article 106213. https://doi.org/10.1016/j.cor.2023.106213

Vancouver

Dokka T, Goerigk M. Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations. Computers and Operations Research. 2023 Jun 30;154:106213. Epub 2023 Mar 14. doi: 10.1016/j.cor.2023.106213

Author

Dokka, Trivikram ; Goerigk, Marc. / Multi-level bottleneck assignment problems : Complexity and sparsity-exploiting formulations. In: Computers and Operations Research. 2023 ; Vol. 154.

Bibtex

@article{4c18c132bc0149a283bbb9d1547288aa,
title = "Multi-level bottleneck assignment problems: Complexity and sparsity-exploiting formulations",
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.",
keywords = "Combinatorial optimization, Bottleneck assignment, Approximation, Computational complexity",
author = "Trivikram Dokka and Marc Goerigk",
year = "2023",
month = jun,
day = "30",
doi = "10.1016/j.cor.2023.106213",
language = "English",
volume = "154",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - Multi-level bottleneck assignment problems

T2 - Complexity and sparsity-exploiting formulations

AU - Dokka, Trivikram

AU - Goerigk, Marc

PY - 2023/6/30

Y1 - 2023/6/30

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

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

KW - Combinatorial optimization

KW - Bottleneck assignment

KW - Approximation

KW - Computational complexity

U2 - 10.1016/j.cor.2023.106213

DO - 10.1016/j.cor.2023.106213

M3 - Journal article

VL - 154

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

M1 - 106213

ER -