Solving the Assignment Problem by Relaxation

DOI10.1287/opre.28.4.969zbMath0441.90062OpenAlexW2095169634MaRDI QIDQ3883896

Walter O. Rom, Ming S. Hung

Publication date: 1980

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.28.4.969

zbMATH Keywords

relaxationassignment problemnetwork flow problemsworst case behavioraverage computation time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Deterministic network models in operations research (90B10)

Related Items (26)

Efficient dual simplex algorithms for the assignment problem ⋮ A shortest augmenting path algorithm for dense and sparse linear assignment problems ⋮ A Lagrangean relaxation method for the constrained assignment problem ⋮ Max-min matching problems with multiple assignments ⋮ The singly constrained assignment problem: An AP basis algorithm ⋮ Bilevel time minimizing assignment problem ⋮ A new algorithm for the assignment problem: An alternative to the Hungarian method ⋮ Fast primal-dual update against local weight update in linear assignment problem and its application ⋮ A BRANCH-AND-BOUND ALGORITHM FOR FINDING ALL OPTIMAL SOLUTIONS OF THE ASSIGNMENT PROBLEM ⋮ Transportation problems which can be solved by the use of hirsch-paths for the dual problems ⋮ Critical objective function values in linear sum assignment problems ⋮ An extended assignment problem considering multiple inputs and outputs ⋮ A genuinely polynomial primal simplex algorithm for the assignment problem ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ A strongly polynomial algorithm for the transportation problem ⋮ A relaxation column signature method for assignment problems ⋮ Bottleneck assignment problems under categorization ⋮ Speeding up the Hungarian algorithm ⋮ The assignment problem under categorized jobs ⋮ A variant of time minimizing assignment problem ⋮ A variation of the assignment problem ⋮ An efficient algorithm for the bipartite matching problem ⋮ An infeasible (exterior point) simplex algorithm for assignment problems ⋮ The auction algorithm: A distributed relaxation method for the assignment problem ⋮ An efficient labeling technique for solving sparse assignment problems ⋮ Microcomputer-based algorithms for large scale shortest path problems

This page was built for publication: Solving the Assignment Problem by Relaxation