Home > Research > Publications & Outputs > Approximating the multi-level bottleneck assign...
View graph of relations

Approximating the multi-level bottleneck assignment problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>1/07/2012
<mark>Journal</mark>Operations Research Letters
Issue number4
Number of pages5
Pages (from-to)282-286
Publication StatusPublished
<mark>Original language</mark>English


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.