A Successive Shortest Path Algorithm for the Assignment Problem.

Abstract

In this paper a new successive shortest path (SSP) algorithm for solving the assignment problem is introduced. A computer implementation of this algorithm has been developed and a discussion of the details of this implementation is provided. Computational results are presented which show this implementation of SSP to be substantially more efficient than several recently developed codes including the best primal simplex code. Also, some new theoretical results are presented which are useful in the implementation of SSP, and it is shown that the algorithm has a computational bound of O(n3), where n is the number of origins. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1980
Accession Number
ADA091312

Entities

People

  • Michael Engquist

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Cyber

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computational Complexity
  • Computer Science
  • Computers
  • Iterations
  • Mathematics
  • Military Research
  • Notation
  • Operations Research
  • Simplex Method
  • Standards
  • United States
  • United States Government
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research