Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0654.90050
Renegar, James
A polynomial-time algorithm, based on Newton's method, for linear programming. (English)
[J] Math. Program., Ser. A 40, No.1, 59-93 (1988). ISSN 0025-5610; ISSN 1436-4646/e

The paper includes a new interior method for linear optimization problems based on Newton's method. A polynomial time bound is proven for this algorithm. The algorithm is compared with the ellipsoid algorithm and with Karmarkar's algorithm. The proposed algorithm is conceptually simpler than either of those algorithms. Furthermore, the bounds are compared. The most important result is the O $(m+n)L)$ bound on the number of iterations where n is the number of variables and m the number of constraints.
[J.Guddat]

MSC 2000:: *90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
65K05 Mathematical programming (numerical methods)

Keywords: interior method; linear optimization; Newton's method; polynomial time bound; ellipsoid algorithm; Karmarkar's algorithm

Cited in: Zbl 0734.65050 Zbl 0714.90059 Zbl 0708.90047 Zbl 0713.90049

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]