HOW GOOD IS THE SIMPLEX ALGORITHM,

Abstract

By constructing long 'increasing' paths on appropriate convex polytopes, It is shown that the simplex algorithm for linear programs (at least with its most commonly used pivot rule) is not a 'good algorithm' in the sense of J. Edmonds. That is, the number of pivots or iterations that may be required is not majorized by any polynomial function of the two parameters that specify the size of the program. (Author)

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1970
Accession Number
AD0706119

Entities

People

  • George J. Minty
  • Victor Klee

Organizations

  • University of Washington

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Approximation (Mathematics)
  • Cooperation
  • Evolutionary Algorithms
  • Heuristic Methods
  • Iterations
  • Linear Programming
  • Mathematics
  • Polynomials
  • Scientific Research
  • Simplex Method

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.