Algorithm for the minimax assignment problem with a sparse rectangular matrix

MaRDI QIDQ580163zbMATH OpenFDO

Authors M. I. Rubinshtein

Publication date 1986

Published in Automation and Remote Control (Search for Journal in Brave)

zbMATH Keywords

minimax assignmentpolynomial algorithmsparse matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Review text

The considered problem may be stated as follows. Given is an \(m\times n\) rectangular matrix A with elements a(i,j). Some of the elements are inadmissible and may remain undefined. A diagonal of this matrix is defined as any collection of m matrix elements such that not two are in the same column or in the same row. A diagonal of the matrix A is admissible if it contains no inadmissible elements. The goal is to find an admissible diagonal with the smallest maximal element. In the paper, a new algorithm for the minimax assignment problem is proposed. It behaves particularly well for sparse and rectangular matrices (i.e. those where there are many inadmissible elements and \(m<n)\).

Recommendations

• A note on Hungarian algorithm for assignment problems
• A new algorithm for the assignment problem: An alternative to the Hungarian method
• Remarks on implementation of O ( n ^1/2 τ) assignment algorithms
• scientific article; zbMATH DE number 176471
• scientific article; zbMATH DE number 3905737

Cited in

(2)

• Solving a combinatorial problem with network flows
• Remarks on implementation of O ( n ^1/2 τ) assignment algorithms

This page was built for publication: Algorithm for the minimax assignment problem with a sparse rectangular matrix

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