A simple complexity proof for a polynomial-time linear programming algorithm
type: Item
instance of: scholarly article
title: A simple complexity proof for a polynomial-time linear programming algorithm
zbMATH Open document ID: 0682.90059
DOI: 10.1016/0167-6377(89)90042-4
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: A variant of Karmarkar's polynomial-time algorithm for linear programming is given. A logarithmic penalty function is attached to the objective function and the resulting nonlinear problem is solved by using a sequence of quadratic approximations. There is a simple proof of complexity of \(O(m^{1/2}L)\) iterations and \(O(m^{3,5}L)\) arithmetic operations, where m is the number of variables and L is the size of the problem encoded in binary.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 49M30
zbMATH DE Number: 4118154
zbMATH Keywords: Karmarkar's polynomial-time algorithm
zbMATH Keywords: logarithmic penalty function
zbMATH Keywords: quadratic approximations
author: Paul Tseng
reviewed by: Morgan A. Hanson
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90042-4
OpenAlex ID: W2041934365
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3657778
cites work: Q5638112
cites work: Enlarging the region of convergence of Newton's method for constrained optimization
cites work: Generation of degenerate linear programming problems
cites work: Gaussian elimination is not optimal
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
cites work: Q3491304
cites work: Q4739657
description: scientific article; zbMATH DE number 4118154