Technical Note—A Polynomial Simplex Method for the Assignment Problem

DOI10.1287/OPRE.31.3.595MaRDI QIDQ3669175zbMATH OpenOpenAlexFDO

Authors Ming S. Hung

Publication date 1983

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

assignment probleminteger cost coefficientspolynomial primal simplex algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Cited in

(17)

• A friendly smoothed analysis of the simplex method
• A polynomial time primal network simplex algorithm for minimum cost flows
• Efficient dual simplex algorithms for the assignment problem
• Exterior point simplex-type algorithms for linear and network optimization problems
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• The auction algorithm for the transportation problem
• An O(n^ 2) active set method for solving a certain parametric quadratic program
• A strongly polynomial simplex method for the linear fractional assignment problem
• A competitive (dual) simplex method for the assignment problem
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• A genuinely polynomial primal simplex algorithm for the assignment problem
• Bounded isotonic median regression
• Algorithms and codes for dense assignment problems: The state of the art
• A new algorithm for the assignment problem: An alternative to the Hungarian method
• Active set algorithms for isotonic regression; a unifying framework
• The auction algorithm: A distributed relaxation method for the assignment problem
• A time-triggered dimension reduction algorithm for the task assignment problem

This page was built for publication: Technical Note—A Polynomial Simplex Method for the Assignment Problem

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