Approximating the multi-level bottleneck assignment problem

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

doi:10.1016/j.orl.2012.04.003

Approximating the multi-level bottleneck assignment problem

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

Research output: Contribution to journal › Article › Academic › peer-review

14 Citations (Scopus)

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, 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.

Original language	English
Pages (from-to)	282-286
Journal	Operations Research Letters
Volume	40
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2012.04.003
Publication status	Published - Jul 2012
Externally published	Yes

Keywords

Bottleneck problem
Multidimensional assignment
Approximation
Computational complexity
Efficient algorithm

Access to Document

10.1016/j.orl.2012.04.003

Cite this

@article{0a15983f1bc54e7a95a7b2b03cf68427,

title = "Approximating the multi-level bottleneck assignment problem",

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, 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.",

keywords = "Bottleneck problem, Multidimensional assignment, Approximation, Computational complexity, Efficient algorithm",

author = "T. Dokka and A. Kouvela and F.C.R. Spieksma",

year = "2012",

month = jul,

doi = "10.1016/j.orl.2012.04.003",

language = "English",

volume = "40",

pages = "282--286",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Approximating the multi-level bottleneck assignment problem

AU - Dokka, T.

AU - Kouvela, A.

AU - Spieksma, F.C.R.

PY - 2012/7

Y1 - 2012/7

N2 - 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.

AB - 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.

KW - Bottleneck problem

KW - Multidimensional assignment

KW - Approximation

KW - Computational complexity

KW - Efficient algorithm

U2 - 10.1016/j.orl.2012.04.003

DO - 10.1016/j.orl.2012.04.003

M3 - Article

SN - 0167-6377

VL - 40

SP - 282

EP - 286

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

Approximating the multi-level bottleneck assignment problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this