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 (19)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Average case optimality