Average case optimality

DOI10.1016/0885-064X(85)90023-8zbMath0586.68040OpenAlexW1999786887MaRDI QIDQ1071513

Grzegorz W. Wasilkowski

Publication date: 1985

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(85)90023-8

zbMATH Keywords

optimal algorithmoptimal informationInformation-based complexityaverage casebounds on the problem complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

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, The average error of quadrature formulas for functions of bounded variation, 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, What is the complexity of ill-posed problems?, Recent developments in information-based complexity, Automatic integration using asymptotically optimal adaptive simpson quadrature, Measures of uncertainty and information in computation, On the average complexity of multivariate problems, Information of varying cardinality, On average case errors in numerical analysis, Adaption allows efficient integration of functions with unknown singularities, The average a posteriori error of numerical methods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Can adaption help on the average?
• Average case optimality for linear problems
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• A survey of information-based complexity
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Optimal solution of nonlinear equations
• Optimal algorithms for linear problems with Gaussian measures
• Information of varying cardinality
• Gaussian measure in Hilbert space and applications in numerical analysis
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• On the average number of steps of the simplex method of linear programming
• On the efficiency of algorithms of analysis
• An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
• The fundamental theorem of algebra and complexity theory
• Elliptically contoured measures on infinite-dimensional Banach spaces
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials