Average case optimality

DOI10.1016/0885-064X(85)90023-8MaRDI QIDQ1071513zbMATH OpenOpenAlexFDO

Authors 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

average caseoptimal algorithmInformation-based complexityoptimal informationbounds on the problem complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Average case optimality for linear problems
• scientific article; zbMATH DE number 193625
• Average-case analysis of numerical problems
• Noisy Information and Computational Complexity
• Recent developments in information-based complexity

Cites work

• 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?)
• 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
• Information of varying cardinality
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• On the average number of steps of the simplex method of linear programming
• On the efficiency of algorithms of analysis
• Optimal algorithms for linear problems with Gaussian measures
• Optimal solution of nonlinear equations
• The fundamental theorem of algebra and complexity theory

Cited in

(25)

• On average case errors in numerical analysis
• The algorithm designer versus nature: A game-theoretic approach to information-based complexity
• On a class of omnibus algorithms for zero-finding
• On average complexity of global optimization problems
• Recent developments in information-based complexity
• Average complexity of divide-and-conquer algorithms
• The average error of quadrature formulas for functions of bounded variation
• Optimal search algorithm for extrema of a discrete periodic bimodal function
• Average-case analysis of numerical problems
• What is the complexity of ill-posed problems?
• Approximation of linear functionals on a Banach space with a Gaussian measure
• A stochastic analog to Chebyshev centers and optimal average case algorithms
• On the average complexity of multivariate problems
• Adaption allows efficient integration of functions with unknown singularities
• On optimal averages
• Average case optimality for linear problems
• For which error criteria can we solve nonlinear equations?
• 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
• Information of varying cardinality
• Measures of uncertainty and information in computation
• Optimal solution of ordinary differential equations
• The average a posteriori error of numerical methods
• A survey of information-based complexity

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)