Solving the Assignment Problem by Relaxation

DOI10.1287/OPRE.28.4.969MaRDI QIDQ3883896zbMATH OpenOpenAlexFDO

Authors Ming S. Hung, Walter O. Rom

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

assignment problemrelaxationnetwork flow problemsworst case behavioraverage computation time

Mathematics Subject Classification ID

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

Cited in

(26)

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

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

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