Approximating the multi-level bottleneck assignment problem

T. Dokka, A. Kouvela, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)


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 m-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.
Original languageEnglish
Pages (from-to)282-286
JournalOperations Research Letters
Issue number4
Publication statusPublished - Jul 2012
Externally publishedYes


  • Bottleneck problem
  • Multidimensional assignment
  • Approximation
  • Computational complexity
  • Efficient algorithm


Dive into the research topics of 'Approximating the multi-level bottleneck assignment problem'. Together they form a unique fingerprint.

Cite this