A simple complexity proof for a polynomial-time linear programming algorithm

DOI10.1016/0167-6377(89)90042-4MaRDI QIDQ1824548zbMATH OpenOpenAlexFDO

Authors Paul Tseng

Publication date 1989

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(89)90042-4

zbMATH Keywords

Karmarkar's polynomial-time algorithmlogarithmic penalty functionquadratic approximations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

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.

Recommendations

• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 898014
• scientific article; zbMATH DE number 4016589
• scientific article; zbMATH DE number 4131946
• scientific article; zbMATH DE number 4082856

Cites work

• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Enlarging the region of convergence of Newton's method for constrained optimization
• Gaussian elimination is not optimal
• Generation of degenerate linear programming problems
• scientific article; zbMATH DE number 4164543 (Why is no real title available?)
• scientific article; zbMATH DE number 3809326 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)

Cited in

(9)

• A proof of the polynomiality of the Iri-Imai method
• Interior dual proximal point algorithm for linear programs
• An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
• scientific article; zbMATH DE number 4131946 (Why is no real title available?)
• scientific article; zbMATH DE number 1471763 (Why is no real title available?)
• scientific article; zbMATH DE number 898014 (Why is no real title available?)
• Solving linear program as linear system in polynomial time
• scientific article; zbMATH DE number 2208706 (Why is no real title available?)
• A simple polynomial-time rescaling algorithm for solving linear programs

This page was built for publication: A simple complexity proof for a polynomial-time linear programming algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1824548)