Approximating the multi-level bottleneck assignment problem
Dokka, Trivikram; Kouvela, Anastasia; and Spieksma, Frits C.R.
(2012)
Approximating the multi-level bottleneck assignment problem.
Operations Research Letters, 40 (4).
pp. 282-286.
ISSN 0167-6377
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.
| Item Type | Article |
|---|---|
| Keywords | ISI,approximation,bottleneck problem,computational complexity,efficient algorithm,multidimensional assignment |
| Departments | LSE |
| DOI | 10.1016/j.orl.2012.04.003 |
| Date Deposited | 23 May 2012 11:04 |
| URI | https://researchonline.lse.ac.uk/id/eprint/43861 |