Probabilistic analysis of a differential equation for linear programming

DOI10.1016/S0885-064X(03)00032-3zbMath1229.90078arXivcs/0110056WikidataQ58455278 ScholiaQ58455278MaRDI QIDQ652446

Shmuel Fishman, Hava T. Siegelmann, Joshua Feinberg, Asa Ben-Hur

Publication date: 14 December 2011

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0110056

zbMATH Keywords

linear programmingdynamical systemsscalingrandom matrix theorytheory of analog computation

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Linear programming (90C05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

Random matrix theory for the analysis of the performance of an analog computer: a scaling theory ⋮ Scaling and universality of the complexity of analog computation ⋮ Analog-symbolic memory that tracks via reconsolidation ⋮ A universal scaling theory for complexity of analog computation ⋮ A theory of complexity for continuous time systems ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of linear programming
• Analog computation with dynamical systems
• A theory of complexity for continuous time systems
• Planar diagrams
• Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
• Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
• Large rectangular random matrices
• On the average number of steps of the simplex method of linear programming
• The Efficiency of the Simplex Method: A Survey
• Dynamical Systems which Solve Optimization Problems with Linear Constraints
• Probabilistic Models for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• Incorporating Condition Measures into the Complexity Theory of Linear Programming