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
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
