Approximating the multi-level bottleneck assignment problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationalgorithms and computation - 6th International Workshop, WALCOM 2012, Proceedings
EditorsM.S. Rahman, S. Nakano
Place of PublicationBerlin
PublisherSpringer
Pages64-75
Number of pages12
ISBN (Electronic)978-3-642-28076-4
ISBN (Print)978-3-642-28075-7
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event6th International Workshop on Algorithms and Computation, WALCOM 2012 - Dhaka, Bangladesh
Duration: 15 Feb 201217 Feb 2012

Publication series

NameLecture Notes in Computer Science
Volume7157
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Workshop on Algorithms and Computation, WALCOM 2012
CountryBangladesh
CityDhaka
Period15/02/1217/02/12

Keywords

  • approximation
  • bottleneck problem
  • computational complexity
  • efficient algorithm
  • multidimensional assignment

Fingerprint

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

Cite this