A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

DOI10.1007/BF01582137zbMath0783.90065OpenAlexW1985372427MaRDI QIDQ689144

Ron Shamir, Ilan Adler

Publication date: 6 December 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

interior point methodClarkson's randomized algorithmfixed dimension optimization

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (7)

Exact primitives for smallest enclosing ellipses ⋮ On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids ⋮ Random sampling with removal ⋮ Provably fast training algorithms for support vector machines ⋮ The Geometry of Differential Privacy: The Small Database and Approximate Cases ⋮ Enumerating a subset of the integer points inside a Minkowski sum ⋮ Minimum-volume enclosing ellipsoids and core sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Constrained global optimization: algorithms and applications
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Geometric algorithms and combinatorial optimization
• A randomized algorithm for fixed-dimensional linear programming
• Convex Analysis

This page was built for publication: A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio