An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
From MaRDI portal
Publication:920841
DOI10.1007/BF01580859zbMath0708.90047OpenAlexW1993982015MaRDI QIDQ920841
Publication date: 1990
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580859
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)
Related Items (61)
A note on the subtree ordered median problem in networks based on nestedness property ⋮ A globally convergent primal-dual interior point algorithm for convex programming ⋮ Tensors in computations ⋮ Interior-point algorithms for semi-infinite programming ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ Solving linear programming problems exactly ⋮ Unnamed Item ⋮ An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming ⋮ Long-step strategies in interior-point primal-dual methods ⋮ On linear programming and matrix scaling over the algebraic numbers ⋮ A polynomial-time algorithm, based on Newton's method, for linear programming ⋮ Interior-point methods: An old and new approach to nonlinear programming ⋮ Approximation algorithms for inventory problems with submodular or routing costs ⋮ Linear programming and the Newton barrier flow ⋮ A projection cutting plane algorithm for convex programming problems ⋮ An extension of predictor-corrector algorithm to a class of convex separable program ⋮ Interior path following primal-dual algorithms. I: Linear programming ⋮ Interior path following primal-dual algorithms. II: Convex quadratic programming ⋮ A polynomial-time algorithm for a class of linear complementarity problems ⋮ A cutting plane algorithm for convex programming that uses analytic centers ⋮ Complexity estimates of some cutting plane methods based on the analytic barrier ⋮ An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Fair Policy Targeting ⋮ Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems ⋮ A direct heuristic algorithm for linear programming ⋮ Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function ⋮ A survey of search directions in interior point methods for linear programming ⋮ An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem ⋮ On the convergence of the affine-scaling algorithm ⋮ A combinatorial interior point method for network flow problems ⋮ Long steps in an \(O(n^ 3L)\) algorithm for linear programming ⋮ A polynomial method of approximate centers for linear programming ⋮ A scaling technique for finding the weighted analytic center of a polytope ⋮ On the finite convergence of interior-point algorithms for linear programming ⋮ Convergence behavior of interior-point algorithms ⋮ The complexity of a special convex programming problem connected with nonlinear optimization ⋮ The analyticity of interior-point-paths at strictly complementary solutions of linear programs ⋮ Complexity of circumscribed and inscribed ellipsoid methods for solving equilibrium economical models ⋮ Locating tree-shaped facilities using the ordered median objective ⋮ Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem ⋮ A new potential reduction algorithm for smooth convex programming ⋮ Interior-point algorithms for a generalization of linear programming and weighted centring ⋮ Men and progress in linear programming ⋮ Containing and shrinking ellipsoids in the path-following algorithm ⋮ Polynomial affine algorithms for linear programming ⋮ A simple complexity proof for a polynomial-time linear programming algorithm ⋮ \(O(n^ 3)\) noniterative heuristic algorithm for linear programs with error-free implementation. ⋮ An exterior-point method for linear programming problems ⋮ O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming ⋮ Enumerating a subset of the integer points inside a Minkowski sum ⋮ An interactive interior point algorithm for multiobjective linear programming problems ⋮ Finding an interior point in the optimal face of linear programs ⋮ A potential-reduction variant of Renegar's short-step path-following method for linear programming ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ On the classical logarithmic barrier function method for a class of smooth convex programming problems ⋮ Interior-point algorithm for quadratically constrained entropy minimization problems ⋮ New approximability results for two-dimensional bin packing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- Systems of distinct representatives and linear algebra
This page was built for publication: An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
