Approximating the multi-level bottleneck assignment problem
Dokka, T., Kouvela, A. & Spieksma, F. C. R.
(2012).
Approximating the multi-level bottleneck assignment problem.
In
Rahman, M. S. & Nakano, S.
(Eds.),
Walcom: Algorithms and Computation: 6th International Workshop, Walcom 2012, Dhaka, Bangladesh, February 15-17, 2012: Proceeding
(pp. 64-75).
Springer Berlin / Heidelberg.
https://doi.org/10.1007/978-3-642-28076-4_9
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. One of the applications described there concerns bus driver scheduling. We view the problem as a special case of a bottleneck m-dimensional multi-index assignment problem. We give approximation algorithms and inapproximability results, depending upon the completeness of the underlying graph.
| Item Type | Chapter |
|---|---|
| Copyright holders | © 2012 Springer-Verlag |
| Departments | LSE |
| DOI | 10.1007/978-3-642-28076-4_9 |
| Date Deposited | 28 Mar 2012 |
| URI | https://researchonline.lse.ac.uk/id/eprint/42871 |
Explore Further
- https://www.scopus.com/pages/publications/84857885830 (Scopus publication)
- http://www.springer.com/ (Official URL)