Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2001-10-31
Physics Letters A, Vol. 323 (2004) pp. 204-209
Physics
Condensed Matter
Statistical Mechanics
8 pages, latex, 2 eps figures; final published version
Scientific paper
10.1016/j.physleta.2004.01.069
The phase space flow of a dynamical system leading to the solution of Linear Programming (LP) problems is explored as an example of complexity analysis in an analog computation framework. An ensemble of LP problems with $n$ variables and $m$ constraints ($n>m$), where all elements of the vectors and matrices are normally distributed is studied. The convergence time of a flow to the fixed point representing the optimal solution is computed. The cumulative distribution ${\cal F}^{(n,m)}(\Delta)$ of the convergence rate $\Delta_{min}$ to this point is calculated analytically, in the asymptotic limit of large $(n,m)$, in the framework of Random Matrix Theory. In this limit ${\cal F}^{(n,m)}(\Delta)$ is found to be a scaling function, namely it is a function of one variable that is a combination of $n$, $m$ and $\Delta$ rather then a function of these three variables separately. From numerical simulations also the distribution of the computation times is calculated and found to be a scaling function as well.
Ben-Hur Asa
Feinberg Joshua
Fishman Shmuel
Siegelmann Hava T.
No associations
LandOfFree
Probabilistic analysis of the phase space flow for linear programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Probabilistic analysis of the phase space flow for linear programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic analysis of the phase space flow for linear programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-104593