Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Approximating the multi-level bottleneck assignment problem
AU - Dokka, Trivikram
AU - Kouvela, Anastasia
AU - Spieksma, Frits C.r.
PY - 2012/7/1
Y1 - 2012/7/1
N2 - We consider the multi-level bottleneck assignment problem (MBA). This problem is described in the recent book “Assignment Problems” by Burkard et al. (2009) on pages 188–189, where its complexity status is called open. We view the problem as a special case of a bottleneck mm-dimensional multi-index assignment problem and settle its complexity status. We give approximation algorithms and inapproximability results, depending upon the completeness of the underlying graph.
AB - We consider the multi-level bottleneck assignment problem (MBA). This problem is described in the recent book “Assignment Problems” by Burkard et al. (2009) on pages 188–189, where its complexity status is called open. We view the problem as a special case of a bottleneck mm-dimensional multi-index assignment problem and settle its complexity status. We give approximation algorithms and inapproximability results, depending upon the completeness of the underlying graph.
KW - Bottleneck problem
KW - Multidimensional assignment
KW - Approximation
KW - Computational complexity
KW - Efficient algorithm
U2 - 10.1016/j.orl.2012.04.003
DO - 10.1016/j.orl.2012.04.003
M3 - Journal article
VL - 40
SP - 282
EP - 286
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 4
ER -