Efficient dual simplex algorithms for the assignment problem

DOI10.1007/BF01582245zbMATH Open0578.90051OpenAlexW4246468160MaRDI QIDQ3701192FDOQ3701192

Authors: Donald Goldfarb 

Publication date: 1985

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

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

Recommendations

• A sequential dual simplex algorithm for the linear assignment problem
• A competitive (dual) simplex method for the assignment problem
• A genuinely polynomial primal simplex algorithm for the assignment problem
• A dual feasible forest algorithm for the linear assignment problem
• scientific article; zbMATH DE number 176471

zbMATH Keywords

assignment problemdual simplex methodweighted matchingblock-pivotimplementation analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Self-Adjusting Heaps
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• Signature Methods for the Assignment Problem
• A network simplex method
• The alternating basis algorithm for assignment problems
• Amortized Computational Complexity
• Solving the Assignment Problem by Relaxation
• A new algorithm for the assignment problem

Cited In (48)

• A relaxation column signature method for assignment problems
• Two kinds of constrained assignment problems
• Strongly polynomial simplex algorithm for bipartite vertex packing
• Title not available (Why is that?)
• On use of assignment algorithms to reconstruct inverse matrices
• Sparse dual transportation polyhedra: Extreme points and signatures
• A faster data assignment algorithm for maximum likelihood-based multitarget motion tracking with bearings-only measurements
• A sequential dual simplex algorithm for the linear assignment problem
• A Phase I That Solves Transportation Problems
• An in-core/out-of-core method for solving large scale assignment problems
• Improving the Hungarian assignment algorithm
• Incremental assignment problem
• On the initialization methods of an exterior point algorithm for the assignment problem
• Heuristic and exact algorithms for the simultaneous assignment problem
• Remarks on implementation of O ( n ^1/2 τ) assignment algorithms
• New approximation results on graph matching and related problems
• Signature classes of transportation polytopes
• A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• Exterior point simplex-type algorithms for linear and network optimization problems
• Personnel placement in a fuzzy environment
• The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm
• The auction algorithm for the transportation problem
• A simple dual algorithm for the generalised assignment problem
• Sinkhorn Algorithm for Lifted Assignment Problems
• On solving a variation of the assignment problem
• The singly constrained assignment problem: An AP basis algorithm
• Title not available (Why is that?)
• Analysis and automatization of the Edmonds algorithm for the assignment problem
• A competitive (dual) simplex method for the assignment problem
• Title not available (Why is that?)
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• Primal-dual algorithms for the assignment problem
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• Solving linear bottleneck assignment problems via strong spanning trees
• A genuinely polynomial primal simplex algorithm for the assignment problem
• A primal-dual simplex method for linear programs
• An infeasible (exterior point) simplex algorithm for assignment problems
• Worst case examples of an exterior point algorithm for the assignment problem
• An efficient algorithm for the symmetric principal minor assignment problem
• Title not available (Why is that?)
• The computational efficiency of Ji-Lee-Li algorithm for the assignment problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• On finding and detecting efficient assignments in the case of multiple inputs and outputs
• A new strongly polynomial dual network simplex algorithm
• A new algorithm for the assignment problem: An alternative to the Hungarian method
• The auction algorithm: A distributed relaxation method for the assignment problem
• Title not available (Why is that?)

This page was built for publication: Efficient dual simplex algorithms for the assignment problem

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