A genuinely polynomial primal simplex algorithm for the assignment problem

DOI10.1016/0166-218X(93)90054-RzbMath0808.90089OpenAlexW2055453466MaRDI QIDQ686416

Mustafa Akgül

Publication date: 6 December 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90054-r

zbMATH Keywords

polynomial algorithmsassignment problemincreasing sequence of subgraphsnetwork simplex methodprimal simplex algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Discrete location and assignment (90B80)

Related Items

A polynomial time primal network simplex algorithm for minimum cost flows, A new pivot selection rule for the network simplex algorithm, A graph space optimal transport distance as a generalization of L ^p distances: application to a seismic imaging inverse problem, Algorithms and codes for dense assignment problems: The state of the art, Exterior point simplex-type algorithms for linear and network optimization problems, Critical objective function values in linear sum assignment problems, A genuinely polynomial primal simplex algorithm for the assignment problem, Collaborative assignment using belief-desire-intention agent modeling and negotiation with speedup strategies, A strongly polynomial simplex method for the linear fractional assignment problem, Sensitivity analysis of the optimal assignment., A review of the use of optimal transport distances for high resolution seismic imaging based on the full waveform

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A genuinely polynomial primal simplex algorithm for the assignment problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Primal-dual algorithms for the assignment problem
• A sequential dual simplex algorithm for the linear assignment problem
• A data structure for dynamic trees
• Algorithms for the Assignment and Transportation Problems
• 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
• A competitive (dual) simplex method for the assignment problem
• Solving the Assignment Problem by Relaxation
• A new algorithm for the assignment problem
• A Recursive Method for Solving Assignment Problems
• A dual feasible forest algorithm for the linear assignment problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A network simplex method
• An algebraic approach to assignment problems
• Cost operator algorithms for the transportation problem
• Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
• The alternating basis algorithm for assignment problems
• Travelling Salesman and Assignment Problems: A Survey
• Theoretical Properties of the Network Simplex Method
• Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
• Optimality and Computation of (σ, S) Policies in the Multi-Item Infinite Horizon Inventory Problem
• On some techniques useful for solution of transportation network problems
• Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems
• Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm