A new polynomial-time algorithm for linear programming
From MaRDI portal
Publication:761967
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
Cites Work
Cited In (only showing first 100 items - show all)
- Classification by polynomial surfaces
- Interior-point algorithms for semi-infinite programming
- An interior point algorithm for semi-infinite linear programming
- A finite steps algorithm for solving convex feasibility problems
- An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming
- Best \(k\)-digit rational bounds for irrational numbers: pre- and super-computer era
- A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
- Exponential lower bounds for polytopes in combinatorial optimization
- Implementation of an inexact approach to solving linear semi-infinite programming problems
- A decision procedure for linear ``big O equations
- A cutting plane algorithm for convex programming that uses analytic centers
- The theory of linear programming:skew symmetric self-dual problems and the central path*
- Abstract tropical linear programming
- Fuzzy stochastic linear programming: survey and future research directions
- A wide neighborhood infeasible-interior-point method with arc-search for linear programming
- On approximating D-induced polar sets of a second-order cone by an ellipsoid
- An improved predictor-corrector interior-point algorithm for linear complementarity problems with \(O(\sqrt{n}L)\)-iteration complexity
- A polynomial arc-search interior-point algorithm for convex quadratic programming
- A new primal-dual predictor-corrector interior-point method for linear programming based on a wide neighbourhood
- An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term
- Scheduling ordered open shops
- A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access
- A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming
- Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term
- Adaptive constraint reduction for convex quadratic programming
- Regularization techniques in interior point methods
- A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
- The interior-point revolution in optimization: History, recent developments, and lasting consequences
- Improving a primal–dual simplex-type algorithm using interior point methods
- A new kind of simple kennel function yielding good iteration bounds for primal-dual interior-point methods
- An unconstrained convex programming view of linear programming
- A 99 line code for discretized Michell truss optimization written in Mathematica
- An interior-point algorithm for linear optimization based on a new barrier function
- Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems
- A counterexample to the Hirsch conjecture
- Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function
- An easy way to teach interior-point methods.
- Exterior point simplex-type algorithms for linear and network optimization problems
- A review of numerical methods for nonlinear partial differential equations
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- Strip packing with precedence constraints and strip packing with release times
- Interior Point Methods for Nonlinear Optimization
- Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource
- Linear programming with entropic perturbation
- A recipe for finding good solutions to MINLPs
- Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a \(P\)-matrix
- A combined phase I-phase II projective algorithm for linear programming
- Computational experience with a modified potential reduction algorithm for linear programming
- Algorithms for the solution of quadratic knapsack problems
- Interior path following primal-dual algorithms. I: Linear programming
- A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem
- Binary classification posed as a quadratically constrained quadratic programming and solved using particle swarm optimization
- Context-content systems of random variables: the contextuality-by-default theory
- Pivot rules for linear programming: A survey on recent theoretical developments
- Selectivity in probabilistic causality: where psychology runs into quantum physics
- A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates.
- Lot-size models with backlogging: Strong reformulations and cutting planes
- A polynomial interior-point algorithm for monotone linear complementarity problems
- An extended variant of Karmarkar's interior point algorithm
- Parallel machine scheduling with splitting jobs
- A survey of dynamic network flows
- Approximation schemes for packing with item fragmentation
- Generalized Bottleneck Problems∗
- Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
- Strong linear programming relaxations for the orienteering problem
- Extension of a projective interior point method for linearly constrained convex programming
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- A relaxed version of Karmarkar's method
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
- Solving combinatorial optimization problems using Karmarkar's algorithm
- An interior method for nonconvex semidefinite programs
- A new efficient primal dual simplex algorithm
- A fuzzy genetic algorithm for driver scheduling
- On the complexity of minmax regret linear programming
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Two design principles of geometric algorithms in finite-precision arithmetic
- Approximating linear programming is log-space complete for P
- Arbitrary-norm separating plane
- Potential-reduction methods in mathematical programming
- Spatial reasoning in a fuzzy region connection calculus
- Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function
- An entire space polynomial-time algorithm for linear programming
- A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
- A new class of preconditioners for large-scale linear systems from interior point methods for linear programming
- Numerically efficient and robust Interior-point algorithm for finite strain rate-independent crystal plasticity
- Lagrangian relaxation based algorithm for trigeneration planning with storages
- Interior point method for solving fuzzy number linear programming problems using linear ranking function
- Comments on ``Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks
- On the entropic perturbation and exponential penalty methods for linear programming
- New complexity analysis of IIPMs for linear optimization based on a specific self-regular function
- Efficient solution of two-stage stochastic linear programs using interior point methods
- A characterization theorem and an algorithm for a convex hull problem
- Large-scale MV efficient frontier computation via a procedure of parametric quadratic programming
- Combining topological and size information for spatial reasoning
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- A weighted-gradient approach to multi-objective linear programming problems using the analytic hierarchy process
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)
