Average case optimality
From MaRDI portal
Information-based complexity studies problems where only partial and contaminated information is available. One simply states how well a problem should be solved and indicates the type of information available. The theory then yields the optimal information, the optimal algorithm, and bounds on the problem complexity. In this paper we discuss some recent results dealing with the average case setting, i.e., the setting where both the cost and the error are measured on the average.
Recommendations
Cites work
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- A survey of information-based complexity
- An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Average case optimality for linear problems
- Can adaption help on the average?
- Elliptically contoured measures on infinite-dimensional Banach spaces
- Gaussian measure in Hilbert space and applications in numerical analysis
- scientific article; zbMATH DE number 3150149 (Why is no real title available?)
- scientific article; zbMATH DE number 3174587 (Why is no real title available?)
- scientific article; zbMATH DE number 3880432 (Why is no real title available?)
- scientific article; zbMATH DE number 4112013 (Why is no real title available?)
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 3574966 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- Information of varying cardinality
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- On the average number of steps of the simplex method of linear programming
- On the efficiency of algorithms of analysis
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- Optimal algorithms for linear problems with Gaussian measures
- Optimal solution of nonlinear equations
- The fundamental theorem of algebra and complexity theory
Cited in
(25)- The average a posteriori error of numerical methods
- A survey of information-based complexity
- Approximation of linear functionals on a Banach space with a Gaussian measure
- For which error criteria can we solve nonlinear equations?
- The algorithm designer versus nature: A game-theoretic approach to information-based complexity
- Optimal solution of ordinary differential equations
- Average complexity of divide-and-conquer algorithms
- A stochastic analog to Chebyshev centers and optimal average case algorithms
- On a class of omnibus algorithms for zero-finding
- Optimal search algorithm for extrema of a discrete periodic bimodal function
- Measures of uncertainty and information in computation
- On optimal averages
- Average-case analysis of numerical problems
- Information of varying cardinality
- On average case errors in numerical analysis
- Adaption allows efficient integration of functions with unknown singularities
- The average error of quadrature formulas for functions of bounded variation
- What is the complexity of ill-posed problems?
- Recent developments in information-based complexity
- scientific article; zbMATH DE number 4112013 (Why is no real title available?)
- Average case behavior of random search for the maximum
- Automatic integration using asymptotically optimal adaptive simpson quadrature
- On average complexity of global optimization problems
- On the average complexity of multivariate problems
- Average case optimality for linear problems
This page was built for publication: Average case optimality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071513)
