Efficient dual simplex algorithms for the assignment problem
From MaRDI portal
Publication:3701192
DOI10.1007/BF01582245zbMath0578.90051OpenAlexW4246468160MaRDI QIDQ3701192
Publication date: 1985
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582245
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items
Improving the Hungarian assignment algorithm, A shortest augmenting path algorithm for dense and sparse linear assignment problems, A competitive (dual) simplex method for the assignment problem, A sequential dual simplex algorithm for the linear assignment problem, Incremental assignment problem, 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, New approximation results on graph matching and related problems, 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, Exterior point simplex-type algorithms for linear and network optimization problems, Personnel placement in a fuzzy environment, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, A genuinely polynomial primal simplex algorithm for the assignment problem, Solving linear bottleneck assignment problems via strong spanning trees, A primal-dual simplex method for linear programs, Signature classes of transportation polytopes, A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements, A relaxation column signature method for assignment problems, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, The auction algorithm: A distributed relaxation method for the assignment problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Technical Note—A Polynomial Simplex Method for the Assignment Problem
- Signature Methods for the Assignment Problem
- Amortized Computational Complexity
- Solving the Assignment Problem by Relaxation
- A new algorithm for the assignment problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- A network simplex method
- The alternating basis algorithm for assignment problems
- Self-Adjusting Heaps
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
