Solution methods and computational investigations for the linear bottleneck assignment problem

DOI10.1007/BF02684443zbMath0894.90127MaRDI QIDQ1377280

Ulrich Pferschy

Publication date: 4 February 1998

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

sparse subgraphsmaximum cardinality matchinglinear bottleneck assignment problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Boolean programming (90C09) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (11)

Sensitivity analysis for bottleneck assignment problems ⋮ Task preference-based bottleneck assignment problem ⋮ An improved algorithm for two stage time minimization assignment problem ⋮ Allocation of indivisible items with individual preference graphs ⋮ Quadratic bottleneck problems ⋮ Selected topics on assignment problems ⋮ Bottleneck flows in unit capacity networks ⋮ A priority based assignment problem ⋮ A priority based unbalanced time minimization assignment problem ⋮ A new matrix bandwidth reduction algorithm ⋮ An alternate approach to solve two-level priority based assignment problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Alternate strategies for solving bottleneck assignment problems - analysis and computational results
• An efficient labeling technique for solving sparse assignment problems
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• An augmenting path method for solving linear bottleneck assignment problems
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• Algorithm for the solution of the assignment problem for sparse matrices
• An in-core/out-of-core method for solving large scale assignment problems
• Algorithms for two bottleneck optimization problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Solution methods and computational investigations for the linear bottleneck assignment problem