Computer Science – Computational Complexity
Scientific paper
2001-10-29
Computer Science
Computational Complexity
1+37 pages, latex, 5 eps figures. Version accepted for publication in the Journal of Complexity. Changes made: Presentation re
Scientific paper
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 that the distribution of the convergence rate is a scaling function, namely it is a function of one variable that is a combination of three parameters: the number of variables, the number of constraints and the convergence rate, rather than a function of these parameters separately. We also estimate numerically the distribution of computation times, namely the time required to reach a vicinity of the attracting fixed point, and find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times.
Ben-Hur Asa
Feinberg Joshua
Fishman Shmuel
Siegelmann Hava T.
No associations
LandOfFree
Probabilistic analysis of a differential equation 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 a differential equation for linear programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic analysis of a differential equation for linear programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-73099