Abstract
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.
This research was supported by OT Grant OT/07/015.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aringhieri, R., Cordone, R.: The multicommodity multilevel bottleneck assignment problem (2004)
Bianco, L., Bielli, M., Mingozzi, A., Ricciardelli, S., Spadoni, M.: A heuristic procedure for the crew rostering problem. European Journal of Operational Research 58, 272–283 (1992)
Bodlaender, H., Jansen, K., Woeginger, G.: Scheduling with incompatible jobs. Discrete Applied Mathematics 55, 219–232 (1994)
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM (2009)
Cappanera, P., Gallo, G.: A multicommodity flow approach to the crew rostering problem. Operations Research 52, 583–596 (2004)
Carraresi, P., Gallo, G.: A multi-level bottleneck assignment approach to the bus drivers rostering problem. European Journal of Operations Research 16, 163–173 (1984)
Goossens, D., Polyakovskiy, S., Spieksma, F., Woeginger, G.: The approximability of three-dimensional assignment problems with bottleneck objective. Optimization Letters 4, 4–17 (2010)
Hsu, W.-L.: Approximation algorithms for the assembly line balancing crew scheduling problem. Mathematics of Operations Research 9, 376–383 (1984)
Jansen, K.: An approximation scheme for bin packing with conflicts. Journal of Combinatorial Optimization 3, 363–377 (1998)
Coffman Jr., E., Yannakakis, M.: Permuting elements within columns of a matrix in order to minimize maximum row sum. Mathematics of Operations Research 9, 384–390 (1984)
Klinz, B., Woeginger, G.: A New Efficiently Solvable Case of the Three-Dimensional Axial Bottleneck Assignment Problem. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS 1995. LNCS, vol. 1120, pp. 150–162. Springer, Heidelberg (1996)
Queyranne, M., Spieksma, F.: Approximation algorithms for multi-index transportation problems with decomposable costs. Discrete Applied Mathematics 76, 239–254 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dokka, T., Kouvela, A., Spieksma, F.C.R. (2012). Approximating the Multi-level Bottleneck Assignment Problem. In: Rahman, M.S., Nakano, Si. (eds) WALCOM: Algorithms and Computation. WALCOM 2012. Lecture Notes in Computer Science, vol 7157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28076-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-28076-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28075-7
Online ISBN: 978-3-642-28076-4
eBook Packages: Computer ScienceComputer Science (R0)