Efficient dual simplex algorithms for the assignment problem

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

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

Cites work

A network simplex method
A new algorithm for the assignment problem
Amortized Computational Complexity
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
scientific article; zbMATH DE number 3643026 (Why is no real title available?)
scientific article; zbMATH DE number 3511563 (Why is no real title available?)
scientific article; zbMATH DE number 3637616 (Why is no real title available?)
scientific article; zbMATH DE number 3231692 (Why is no real title available?)
Self-Adjusting Heaps
Signature Methods for the Assignment Problem
Solving the Assignment Problem by Relaxation
Technical Note—A Polynomial Simplex Method for the Assignment Problem
The alternating basis algorithm for assignment problems
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(48)

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

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)