A sequential dual simplex algorithm for the linear assignment problem
The linear assignment problem is viewed as an instance of the transshipment problem over a directed bipartite graph G. First the corresponding dual simplex method and its relationship to graphs is described in detail. This method starts with a dual feasible tree (paragraph 1). As a preliminary the already known ``strongly feasible trees and the ``dual strongly feasible trees for the assignment problem are introduced, certain properties are derived and the dual simplex algorithm of Balinski, which works in stages is described. The main result consists of a new algorithm (paragraph 2) which also works with dual strongly feasible trees; but here a sequence of assignment problems over an increasing sequence of graphs each of which defines such a problem is solved. This algorithm gives the possibility to handle rectangular systems (i.e. for the set of vertices \(N=U\cup V\) of G the sizes of U and V are different) in a natural manner, i.e. without any transformations which, for example, needs the Hungarian algorithm. Finally (paragraph 3) it is shown that the developed algorithm works with \(O(n^ 2)\) pivots and \(O(n^ 2\log n+nm)\) time complexity, i.e. the same complexity as other algorithms known in the literature.
- Efficient dual simplex algorithms for the assignment problem
- On dual solutions of the linear assignment problem
- A competitive (dual) simplex method for the assignment problem
- A simple dual algorithm for the generalised assignment problem
- A Dual Simplex Algorithm for Piecewise-Linear Programming
- scientific article; zbMATH DE number 56167
- A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming
- scientific article; zbMATH DE number 3922378
- A dual version of Tardos's algorithm for linear programming
- scientific article; zbMATH DE number 515938
- A competitive (dual) simplex method for the assignment problem
- A network simplex method
- Efficient dual simplex algorithms for the assignment problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- Signature Methods for the Assignment Problem
- The alternating basis algorithm for assignment problems
- A strongly polynomial simplex method for the linear fractional assignment problem
- A simple dual algorithm for the generalised assignment problem
- Algorithms and codes for dense assignment problems: The state of the art
- The computational efficiency of Ji-Lee-Li algorithm for the assignment problem
- scientific article; zbMATH DE number 3922378 (Why is no real title available?)
- Efficient dual simplex algorithms 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 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 dual feasible forest algorithm for the linear assignment problem
- scientific article; zbMATH DE number 176471 (Why is no real title available?)
- scientific article; zbMATH DE number 1795712 (Why is no real title available?)
- On the initialization methods of an exterior point algorithm for the assignment problem
- A genuinely polynomial primal simplex algorithm for the assignment problem
- A primal-dual simplex method for linear programs
- On dual solutions of the linear assignment problem
This page was built for publication: A sequential dual simplex algorithm for the linear assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108928)
