Approximating the multi-level bottleneck assignment problem
Dokka, T., Kouvela, A. & Spieksma, F. C.
(2012).
Approximating the multi-level bottleneck assignment problem.
Operations Research Letters,
40(4), 282-286.
https://doi.org/10.1016/j.orl.2012.04.003
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 |
|---|---|
| Copyright holders | © 2012 Elsevier |
| Departments | LSE |
| DOI | 10.1016/j.orl.2012.04.003 |
| Date Deposited | 23 May 2012 |
| URI | https://researchonline.lse.ac.uk/id/eprint/43861 |
Explore Further
- https://www.scopus.com/pages/publications/84861529150 (Scopus publication)
- http://www.journals.elsevier.com/operations-resear... (Official URL)