Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
Probabilistic Analysis Of A Differential Equation For Linear Programming, Asa Ben-Hur, Joshua Feinberg, Shmuel Fishman, Hava Siegelmann
Probabilistic Analysis Of A Differential Equation For Linear Programming, Asa Ben-Hur, Joshua Feinberg, Shmuel Fishman, Hava Siegelmann
Hava Siegelmann
In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find the surprising result that the distribution of the convergence rate is a scaling function of a single variable. This …