Khachian's Algorithm for Linear Programming.

Abstract

L. G. Khachian's algorithm to check the solvability of a system of linear inequalities with integral coefficients is described. The running time of the algorithm is polynomial in the number of digits of the coefficients. It can be applied to solve linear programs in polynomial time. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA075171

Entities

People

  • Laszlo Lovasz
  • Peter Gacs

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Heuristic Methods
  • Inequalities
  • Integrals
  • Linear Programming
  • Military Research
  • Polynomials

Readers

  • Calculus or Mathematical Analysis
  • Mathematical Modeling and Probability Theory.