A new polynomial-time algorithm for linear programming

DOI10.1007/BF02579150zbMATH Open0557.90065OpenAlexW2611147814WikidataQ29543194 ScholiaQ29543194MaRDI QIDQ761967FDOQ761967

Authors: Narendra K. Karmarkar 

Publication date: 1984

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579150

Recommendations

• scientific article; zbMATH DE number 4016589
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• scientific article; zbMATH DE number 938987
• A polynomial-time algorithm, based on Newton's method, for linear programming
• scientific article; zbMATH DE number 4119927

zbMATH Keywords

computational complexityinterior point methodpolynomial time algorithmnear optimal solution

Mathematics Subject Classification ID

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

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization
• Smoothed analysis of condition numbers and complexity implications for linear programming
• An interior-point algorithm for nonlinear minimax problems
• Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term
• A strongly polynomial algorithm for linear systems having a binary solution
• A simple polynomial-time rescaling algorithm for solving linear programs
• A dynamic large-update primal‐dual interior-point method for linear optimization
• A powerful force-based approach for the limit analysis of three-dimensional frames
• An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
• A self-adjusting primal–dual interior point method for linear programs
• Boolean functions with a simple certificate for CNF complexity
• A matrix generation approach for eigenvalue optimization
• Criss-cross methods: A fresh view on pivot algorithms
• Computation of channel capacity based on self-concordant functions
• Gradient-type methods: a unified perspective in computer science and numerical analysis
• Time-cost trade-off analysis of project networks in fuzzy environments
• Approximation in normed linear spaces
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• An adaptive self-regular proximity-based large-update IPM for LO
• An adaptive infeasible interior-point algorithm with full Nesterov-Todd step for semidefinite optimization
• Method of centers for minimizing generalized eigenvalues
• Convergence behavior of interior-point algorithms
• An adaptive-step primal-dual interior point algorithm for linear optimization
• Hopfield neural networks in large-scale linear optimization problems
• The augmented system variant of IPMs in two-stage stochastic linear programming computation
• Red-blue covering problems and the consecutive ones property
• Interval-valued degrees of belief: applications of interval computations to expert systems and intelligent control
• Quasi-Newton methods for solving underdetermined nonlinear simultaneous equations
• Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
• A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function
• Efficient solution of second order cone program for model predictive control
• An interior-exterior approach for convex quadratic programming
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Efficient implementation and benchmark of interior point methods for the polynomial \(L_{1}\) fitting problem.
• An efficient search direction for linear programming problems
• Conical projection algorithms for linear programming
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Symmetric indefinite systems for interior point methods
• An implementation of Karmarkar's algorithm for linear programming
• A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization
• An interior-point method for semi-infinite programming problems
• On the convergence of the coordinate descent method for convex differentiable minimization
• Utility function programs and optimization over the efficient set in multiple-objective decision making
• A potential-reduction variant of Renegar's short-step path-following method for linear programming
• On scaled projections and pseudoinverses
• KBO orientability
• Full Nesterov-Todd step feasible interior-point algorithm for symmetric cone horizontal linear complementarity problem based on a positive-asymptotic barrier function
• A ``build-down scheme for linear programming
• A predictor-corrector algorithm with multiple corrections for convex quadratic programming
• A polynomial-time algorithm for linear optimization based on a new class of kernel functions
• Book Review: The basic George B. Dantzig
• \(k\)-violation linear programming
• A QMR-based interior-point algorithm for solving linear programs
• A new polynomial time method for a linear complementarity problem
• On the augmented system approach to sparse least-squares problems
• Computing upper and lower bounds in interval decision trees
• Artificial time integration
• Multiple criteria decision support -- a review
• An interior point multiplicative method for optimization under positivity constraints
• Incentive Stackelberg mean-payoff games
• A simple proof of a primal affine scaling method
• Artificial-free simplex algorithm based on the non-acute constraint relaxation
• Detecting ``dense columns in interior point methods for linear programs
• Solving a class of LP problems with a primal-dual logarithmic barrier method
• Computing a quasi-perfect equilibrium of a two-player game
• A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming
• The asymptotic optimal partition and extensions of the nonsubstitution theorem
• A heuristic procedure for the crew rostering problem
• A PRIMAL-DUAL INTERIOR-POINT ALGORITHM BASED ON A NEW KERNEL FUNCTION
• Simple search methods for finding a Nash equilibrium
• A polynomial algorithm for convex quadratic optimization subject to linear inequalities
• A new class of polynomial primal-dual methods for linear and semidefinite optimization
• Partially observable Markov decision processes with imprecise parameters
• An inexact approach to solving linear semi-infinite programming problems
• A geometric view of parametric linear programming
• An interior point potential reduction algorithm for the linear complementarity problem
• Exploiting special structure in a primal-dual path-following algorithm
• Static analysis by abstract interpretation: a mathematical programming approach
• Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization
• Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming
• A practical implementation of stochastic programming: an application to the evaluation of option contracts in supply chains
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• Linear programming, complexity theory and elementary functional analysis
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Layout optimization of large‐scale pin‐jointed frames
• Feasible partition problem in reverse convex and convex mixed-integer programming
• On well definedness of the central path
• A unified mathematical programming formulation of strain driven and interior point algorithms for shakedown and limit analysis
• An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization
• Condition numbers for polyhedra with real number data
• The method of global equilibrium search
• Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
• Parameter estimation in stochastic differential equations
• AN INTERIOR POINT APPROACH FOR SEMIDEFINITE OPTIMIZATION USING NEW PROXIMITY FUNCTIONS
• The central path visits all the vertices of the Klee–Minty cube
• A Frisch-Newton algorithm for sparse quantile regression
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices
• A simple direct cosine simplex algorithm
• Fuzzy goal programming: complementary slackness conditions and computational schemes

This page was built for publication: A new polynomial-time algorithm for linear programming

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