A new polynomial-time algorithm for linear programming
From MaRDI portal
Publication:761967
DOI10.1007/BF02579150zbMath0557.90065OpenAlexW2611147814WikidataQ29543194 ScholiaQ29543194MaRDI QIDQ761967
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579150
Related Items (only showing first 100 items - show all)
An introduction to the analysis of approximation algorithms ⋮ Introduction: New approaches to linear programming ⋮ A different convergence proof of the projective method for linear programming ⋮ A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm ⋮ The iterative step in the linear programming algorithm of N. Karmarkar ⋮ Polynomial-time algorithms for regular set-covering and threshold synthesis ⋮ A reduced-gradient variant of Karmarkar's algorithm and null-space projections ⋮ An extension of Karmarkar's algorithm for linear programming using dual variables ⋮ Karmarkar's algorithm and its place in applied mathematics ⋮ Homotopy techniques in linear programming ⋮ A projective method for linear programming with box-type constraints ⋮ Computational experience with a dual affine variant of Karmarkar's method for linear programming ⋮ An LP-based successive overrelaxation method for linear complementarity problems ⋮ A polynomial Newton method for linear programming ⋮ Karmarkar's algorithm and the ellipsoid method ⋮ Convergence results and numerical experiments on a linear programming hybrid algorithm ⋮ A note on the Edmonds-Fukuda pivoting rule for simplex algorithms ⋮ Implementing an affine scaling algorithm for linear programming ⋮ A new family of exponential LP problems ⋮ Karmarkar's projective algorithm: A null space variant for multi- commodity generalized networks ⋮ A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps ⋮ A multiplicative barrier function method for linear programming ⋮ Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value ⋮ A fully polynomial time projective method ⋮ Exploiting special structure in Karmarkar's linear programming algorithm ⋮ An analog of Karmarkar's algorithm for inequality constrained liner programs, with a `new' class of projective transformations for centering a polytope ⋮ Randomized rounding: A technique for provably good algorithms and algorithmic proofs ⋮ An accelerated successive orthogonal projections method for solving large-scale linear feasibility problems ⋮ Computing Karmarkar projections quickly ⋮ Performance evaluation of concurrent systems using conflict-free and persistent Petri nets ⋮ A relaxed version of Karmarkar's method ⋮ A polynomial-time algorithm, based on Newton's method, for linear programming ⋮ Some remarks on Karmarkar's potential function ⋮ Linear programming and the Newton barrier flow ⋮ On the convexity of the multiplicative version of Karmarkar's potential function ⋮ On scaled projections and pseudoinverses ⋮ Probabilistic construction of deterministic algorithms: approximating packing integer programs ⋮ Eliminating columns in the simplex method for linear programming ⋮ An analysis of an available set of linear programming test problems ⋮ Determining basic variables of optimal solutions in Karmarkar's new LP algorithm ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ A combined phase I-phase II projective algorithm for linear programming ⋮ Lot-size models with backlogging: Strong reformulations and cutting planes ⋮ Projection method for solving systems of linear inequalities ⋮ Conical projection algorithms for linear programming ⋮ Recognition problems for special classes of polynomials in 0-1 variables ⋮ An extension of Karmarkar's projective algorithm for convex quadratic programming ⋮ The Boolean quadratic polytope: Some characteristics, facets and relatives ⋮ Subspaces with well-scaled frames ⋮ Interior path following primal-dual algorithms. I: Linear programming ⋮ Interior path following primal-dual algorithms. II: Convex quadratic programming ⋮ Cutting planes and column generation techniques with the projective algorithm ⋮ Least squares matching problems ⋮ A polynomial-time algorithm for a class of linear complementarity problems ⋮ An interior point algorithm for semi-infinite linear programming ⋮ On the augmented system approach to sparse least-squares problems ⋮ Are analog neural networks better than binary neural networks? ⋮ Solving a class of LP problems with a primal-dual logarithmic barrier method ⋮ Solving a bilevel linear program when the inner decision maker control few variables ⋮ On some efficient interior point methods for nonlinear convex programming ⋮ An optimal-basis identification technique for interior-point linear programming algorithms ⋮ Decomposing finitely generated integral monoids by elimination ⋮ Karmarkar's linear programming algorithm and Newton's method ⋮ An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems ⋮ A primal projective interior point method for linear programming ⋮ Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function ⋮ A new approach to uncertain parameter linear programming ⋮ Solving linear programming problems via linear minimax problems ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ Semidefinite programming and arithmetic circuit evaluation ⋮ Active constraint set invariancy sensitivity analysis in linear optimization ⋮ Euclidean centers: Computation, properties and a MOLP application ⋮ George B. Dantzig and systems optimization ⋮ George Dantzig's impact on the theory of computation ⋮ The \(\ell_1\) solution of linear inequalities ⋮ An interior-point algorithm for nonlinear minimax problems ⋮ Soft arc consistency revisited ⋮ Sparse approximate solution of partial differential equations ⋮ Sparse QR factorization on a massively parallel computer ⋮ A PTAS for the chance-constrained knapsack problem with random item sizes ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ Extension of a projective interior point method for linearly constrained convex programming ⋮ Adaptive large-neighborhood self-regular predictor-corrector interior-point methods for linear optimization ⋮ Finding positive matrices subject to linear restrictions ⋮ An interior-point method for the single-facility location problem with mixed norms using a conic formulation ⋮ Open problems in computational linear algebra ⋮ A polynomial-time algorithm for linear optimization based on a new class of kernel functions ⋮ A globally convergent interior point algorithm for non-convex nonlinear programming ⋮ Exploring complexity of large update interior-point methods for \(P_*(\kappa )\) linear complementarity problem based on kernel function ⋮ A redundant Klee-Minty construction with all the redundant constraints touching the feasible region ⋮ Predictive control for hybrid systems. Implications of polyhedral pre-computations ⋮ The \(C^m\) norm of a function with prescribed jets. II ⋮ Red-blue covering problems and the consecutive ones property ⋮ Partially observable Markov decision processes with imprecise parameters ⋮ Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension ⋮ Consistency of a linear system of inequalities ⋮ Applications of fuzzy set theory to mathematical programming ⋮ A polynomial feasibility test for preemptive periodic scheduling of unrelated processors ⋮ Graph isomorphism and theorems of Birkhoff type ⋮ Intelligent gradient search in linear programming
Cites Work
This page was built for publication: A new polynomial-time algorithm for linear programming
