A simple polynomial-time rescaling algorithm for solving linear programs

DOI10.1145/1007352.1007404MaRDI QIDQ5901080zbMATH OpenOpenAlexFDO

Authors John Dunagan, Santosh S. Vempala

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007404

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Cited in

(8)

• Conditioning of random conic systems under a general family of input distributions
• Statistical active learning algorithms for noise tolerance and differential privacy
• A complete characterization of statistical query learning with applications to evolvability
• On the Power of Learning from k-Wise Queries
• Examples with decreasing largest inscribed ball for deterministic rescaling algorithms
• Smoothed analysis of condition numbers and complexity implications for linear programming
• A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
• A unified worst case for classical simplex and policy iteration pivot rules

This page was built for publication: A simple polynomial-time rescaling algorithm for solving linear programs

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