O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming
type: Item
instance of: scholarly article
title: O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming
zbMATH Open document ID: 0728.65057
DOI: 10.1016/0024-3795(91)90273-Y
author: Shinji Mizuno
published in: Linear Algebra and its Applications
publication date: 1991-01-01T00:00:00Z
review text: Two kinds of O(n\({}^ 3L)\)-operation algorithms are proposed. These algorithms generalize those proposed by \textit{Y. Ye} [An \(O(n^ 3L)\) potential reduction algorithm for linear programming, Math. Programm., Ser. A 50, No.2, 239-258 (1991)] and by \textit{K. M. Anstreicher} and \textit{R. A. Bosch} [Long steps in a \(O(n^ 3L)\) algorithm for linear programming. Yale School of Management, New Haven, Conn. (1989)] in two ways. One is the generalization of the potential function by a parameter on which the search direction also depends. The other is the generalization of the step size in primal space also by a parameter.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4203602
zbMATH Keywords: linear programming
zbMATH Keywords: Karmarkar-algorithm
zbMATH Keywords: potential reduction algorithm
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: \(O(n^ 3L)\)-operation algorithms
Wikidata QID: Q112879926
reviewed by: Johannes Terno
MaRDI profile type: Publication
cites work: A new polynomial-time algorithm for linear programming
cites work: An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
cites work: A polynomial-time algorithm for a class of linear complementarity problems
cites work: A new polynomial time method for a linear complementarity problem
cites work: AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
cites work: Interior path following primal-dual algorithms. I: Linear programming
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: A Centered Projective Algorithm 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
description: scientific article; zbMATH DE number 4203602