A simple polynomial-time rescaling algorithm for solving linear programs

DOI10.1007/s10107-007-0095-7zbMath1157.90007OpenAlexW2069730673MaRDI QIDQ5900037

Santosh Vempala, John Dunagan

Publication date: 3 June 2008

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

Full work available at URL: https://doi.org/10.1007/s10107-007-0095-7

zbMATH Keywords

perceptron algorithmgreedy method

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Linear programming (90C05)

Related Items (17)

Implementation of a projection and rescaling algorithm for second-order conic feasibility problems ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ A simple method for convex optimization in the oracle model ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Solving conic systems via projection and rescaling ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ Adversarial manifold estimation ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ A deterministic rescaled perceptron algorithm ⋮ Geometric Rescaling Algorithms for Submodular Function Minimization ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ Multidimensional Binary Search for Contextual Decision-Making ⋮ Method of Alternating Contractions and Its Applications to Some Convex Optimization Problems ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems

Cites Work

• A new polynomial-time algorithm for linear programming
• Geometric algorithms and combinatorial optimization
• A polynomial-time algorithm for learning noisy linear threshold functions
• The computational complexity of propositional STRIPS planning
• A new algorithm for minimizing convex functions over convex sets
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• Perceptron, Winnow, and PAC Learning
• The Relaxation Method for Solving Systems of Linear Inequalities
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• The Relaxation Method for Linear Inequalities
• Solving convex programs by random walks
• A new condition number for linear programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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