On a Soviet Algorithm for the Linear Programming Problem,

Abstract

Science reported ('Mathematicians Amazed by Russian's Discovery', Science 206,545 (1979)) a new algorithm 'of great theoretical and probably practical importance' for the solution of linear programming problems. The algorithm was ascribed to a Soviet mathematician L. G. Khachian. We have received numerous inquiries from people in business, government and universities concerning this algorithm. Here we shall confine ourselves to answering only two questions: What is the practical value of this algorithm and what is its history? We answer each of these in turn. Our analysis and preliminary experimentation indicate that the method is not of practical interest. It is possible that the ideas of the Soviet method, in combination with new ideas, will eventually lead to a method competitive with Simplex. But that is not the case today. We believe referring to this as Khachian's method is incorrect. Since five Soviet mathematicians have contributed, we propose naming this the 'Soviet Algorithm'.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1979
Accession Number
ADA087058

Entities

People

  • H. Wozniakowski
  • Joseph F. Traub

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computer Programming
  • Computer Science
  • Computers
  • Ellipsoids
  • Linear Programming
  • Military Research
  • New York
  • Simplex Method
  • Universities

Readers

  • Educational Psychology
  • Library and Information Science
  • Operations Research