A competitive (dual) simplex method for the assignment problem

DOI10.1007/BF01580579zbMath0596.90064OpenAlexW2047029951MaRDI QIDQ3730345

Michel Balinski

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580579

zbMATH Keywords

signaturesimplex methodworst case complexitylinear assignmentdual simplex methodaverage number of pivotsnew pivot choice rules

Mathematics Subject Classification ID

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

Related Items

A sequential dual simplex algorithm for the linear assignment problem, The singly constrained assignment problem: An AP basis algorithm, A new strongly polynomial dual network simplex algorithm, A new algorithm for the assignment problem: An alternative to the Hungarian method, Strongly polynomial simplex algorithm for bipartite vertex packing, On solving a variation of the assignment problem, On the initialization methods of an exterior point algorithm for the assignment problem, Transportation problems which can be solved by the use of hirsch-paths for the dual problems, Sparse dual transportation polyhedra: Extreme points and signatures, The auction algorithm for the transportation problem, Algorithms and codes for dense assignment problems: The state of the art, Worst case examples of an exterior point algorithm for the assignment problem, Personnel placement in a fuzzy environment, An extended assignment problem considering multiple inputs and outputs, A genuinely polynomial primal simplex algorithm for the assignment problem, Solving linear bottleneck assignment problems via strong spanning trees, Signature classes of transportation polytopes, Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times, Numerical resolution of an “unbalanced” mass transport problem, A combinatorial algorithm for the Euler equations of incompressible flows, Active set algorithms for isotonic regression; a unifying framework, A relaxation column signature method for assignment problems, Adaptivity with moving grids, Bounded isotonic median regression, An infeasible (exterior point) simplex algorithm for assignment problems, The auction algorithm: A distributed relaxation method for the assignment problem, An \(O(n^ 2)\) active set method for solving a certain parametric quadratic program

Cites Work

• Unnamed Item
• Faces of dual transportation polyhedra
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• Efficient dual simplex algorithms for the assignment problem
• Signature Methods for the Assignment Problem
• On the simplex algorithm for networks and generalized networks
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A network simplex method
• The alternating basis algorithm for assignment problems
• Theoretical Properties of the Network Simplex Method