A sequential dual simplex algorithm for the linear assignment problem
type: Item
instance of: scholarly article
title: A sequential dual simplex algorithm for the linear assignment problem
zbMATH Open document ID: 0654.90053
DOI: 10.1016/0167-6377(88)90082-X
author: Mustafa Akgül
published in: Operations Research Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4068608
zbMATH Keywords: linear assignment problem
zbMATH Keywords: transshipment
zbMATH Keywords: directed bipartite graph
zbMATH Keywords: dual simplex method
zbMATH Keywords: dual strongly feasible trees
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Signature Methods for the Assignment Problem
cites work: A competitive (dual) simplex method for the assignment problem
cites work: The alternating basis algorithm for assignment problems
cites work: A network simplex method
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Efficient dual simplex algorithms for the assignment problem
cites work: Q3707420
Recommended article: Efficient dual simplex algorithms for the assignment problem
Recommended article: On dual solutions of the linear assignment problem
Recommended article: A competitive (dual) simplex method for the assignment problem
Recommended article: A simple dual algorithm for the generalised assignment problem
Recommended article: A Dual Simplex Algorithm for Piecewise-Linear Programming
Recommended article: Q4006619
Recommended article: A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming
Recommended article: Q3696867
Recommended article: A dual version of Tardos's algorithm for linear programming
Recommended article: Q4283454
description: scientific article; zbMATH DE number 4068608