Alternate strategies for solving bottleneck assignment problems - analysis and computational results

DOI10.1007/BF02240182MaRDI QIDQ798564zbMATH OpenOpenAlexFDO

Authors Ulrich Derigs

Publication date 1984

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02240182

zbMATH Keywords

bottleneck assignmentcomputational behaviourcomputational resultscomputational studyhybrid procedurelabeling techniqueshortest augmenting path concepttheoretical equivalencethreshold method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Review text

We analyze two strategies for solving the bottleneck assignment problem - the threshold method and the shortest augmenting path concept -, show their theoretical equivalence and computational behaviour. We develop a new rather efficient labeling technique to be used in the shortest augmenting path method and a hybrid procedure combining the advantages of both concepts. Extensive computational results are reported.

Recommendations

• Solution methods and computational investigations for the linear bottleneck assignment problem
• Threshold assignment algorithm
• Bottleneck assignment problems under categorization
• Multiple bottleneck assignment problem
• Solving linear bottleneck assignment problems via strong spanning trees

Cites work

• An augmenting path method for solving linear bottleneck assignment problems
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis

Cited in

(9)

• An efficient Dijkstra-like labeling method for computing shortest odd/even paths
• Solution methods and computational investigations for the linear bottleneck assignment problem
• The bottleneck generalized assignment problem
• An alternate approach to solve two-level priority based assignment problem
• A priority based assignment problem
• A priority based unbalanced time minimization assignment problem
• An improved algorithm for two stage time minimization assignment problem
• The random linear bottleneck assignment problem
• Selected topics on assignment problems

This page was built for publication: Alternate strategies for solving bottleneck assignment problems - analysis and computational results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798564)