A universal scaling theory for complexity of analog computation
From MaRDI portal
Publication:716028
DOI10.1016/J.PHYSLETA.2007.06.032zbMATH Open1209.90361arXivcond-mat/0508152OpenAlexW2006053240MaRDI QIDQ716028FDOQ716028
Authors: Yaniv S. Avizrats, Shmuel Fishman, Joshua Feinberg 
Publication date: 19 April 2011
Published in: Physics Letters. A (Search for Journal in Brave)
Abstract: We discuss the computational complexity of solving linear programming problems by means of an analog computer. The latter is modeled by a dynamical system which converges to the optimal vertex solution. We analyze various probability ensembles of linear programming problems. For each one of these we obtain numerically the probability distribution functions of certain quantities which measure the complexity. Remarkably, in the asymptotic limit of very large problems, each of these probability distribution functions reduces to a universal scaling function, depending on a single scaling variable and independent of the details of its parent probability ensemble. These functions are reminiscent of the scaling functions familiar in the theory of phase transitions. The results reported here extend analytical and numerical results obtained recently for the Gaussian ensemble.
Full work available at URL: https://arxiv.org/abs/cond-mat/0508152
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Efficiency of the Simplex Method: A Survey
- Title not available (Why is that?)
- Probabilistic Models for Linear Programming
- A theory of complexity for continuous time systems
- Dynamical Systems which Solve Optimization Problems with Linear Constraints
- Probabilistic analysis of a differential equation for linear programming
- Hamiltonian structure of dynamical systems which solve linear programming problems
- Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
- Title not available (Why is that?)
Cited In (6)
- The complexity of analog computation
- Computability of analog networks
- Linear growth of circuit complexity from Brownian dynamics
- An analog solution of programming problems
- Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
- Probabilistic analysis of a differential equation for linear programming
This page was built for publication: A universal scaling theory for complexity of analog computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716028)
