zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A new polynomial-time algorithm for linear programming. (English) Zbl 0557.90065

This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is 0(n 3·5 L) arithmetic operations on 0(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The complexity bound for this algorithm is better than that for the ellipsoid algorithm by a factor of 0(n 2·5 )·

The author shows that every LP can be transformed into the form: min cx subject to xΩΔ, where Ω is the subspace { x:Ax=0} and Δ is the simplex { x:x0 and Σx j =1}, and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form.

Let a 0 =(1/n)e, where e is the vector of all 1’s in R n . Let B(a 0 ,r), B(a 0 ,R) be respectively the largest sphere with center a 0 lying in Δ, and the smallest sphere with center a 0 containing Δ. Then R/r=(n-1). Using this he shows that if a 0 is feasible, a 0 -rc ^, where c ^ is the normalized vector which in the orthogonal projection of c in Ω, is chosen to the minimum objective value by a factor of (1-1/(n-1)). This is the main result on which the algorithm is based.

The algorithm is initiated with a feasible solution x 0 >0, and it generates a descent sequence of positive feasible points x 0 ,x 1 ,··.. In the kth step, the point x k is brought into the center of the simplex by a projective transformation, a step of the form described above is taken, and the inverse projective transformation is applied, leading to the next point x k+1 , reducing the objective function value by a factor of 0(n). The sequence of points generated, converges to a near optimal solution in polynomial time.

Reviewer: K.G.Murty

MSC:
90C05Linear programming
68Q25Analysis of algorithms and problem complexity
References:
[1]H. S. M. Coxeter,Introduction to Geometry, Wiley (1961).
[2]G. B. Dantzig,Linear Programming and Extensions, Princeton University Press, Princeton, NJ (1963).
[3]M. Grötschel, L. Lovász andA. Schrijver, The Ellipsoid Method and its Consequences in Combinatorial Optimization,Combinatorica 1 (1981), 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[4]L. G. Khachiyan, A polynomial Algorithm in Linear Programming,Doklady Akademii Nauk SSSR 244:S (1979), 1093–1096, translated inSoviet Mathematics Doklady 20:1 (1979), 191–194.
[5]V. Klee andG. L. Minty, How good is the simplex algorithm? inInequalities III, (ed. O. Shisha) Academic Press, New York, 1972, 159–179.
[6]O. Veblen andJ. W. Young,Projective Geometry, 1–2, Blaisdell, New York, (1938).
[7]R. J. Walker,Algebraic Curves, Princeton University Press (1950).