Average case optimality
type: Item
instance of: scholarly article
title: Average case optimality
zbMATH Open document ID: 0586.68040
DOI: 10.1016/0885-064X(85)90023-8
published in: Journal of Complexity
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3940725
zbMATH Keywords: Information-based complexity
zbMATH Keywords: optimal information
zbMATH Keywords: optimal algorithm
zbMATH Keywords: bounds on the problem complexity
zbMATH Keywords: average case
author: Grzegorz W. Wasilkowski
MaRDI profile type: Publication
cites work: Elliptically contoured measures on infinite-dimensional Banach spaces
cites work: Q3835022
cites work: Can adaption help on the average?
cites work: Q4144785
cites work: An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
cites work: Monte-Carlo algorithms for the planar multiterminal network reliability problem
cites work: Gaussian measure in Hilbert space and applications in numerical analysis
cites work: Approximation of linear functionals on a Banach space with a Gaussian measure
cites work: Q4164569
cites work: On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
cites work: Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
cites work: Optimal solution of nonlinear equations
cites work: The fundamental theorem of algebra and complexity theory
cites work: Q3346084
cites work: On the average number of steps of the simplex method of linear programming
cites work: On the efficiency of algorithms of analysis
cites work: Q3267545
cites work: Q3293495
cites work: Q3883494
cites work: Average case optimality for linear problems
cites work: Optimal algorithms for linear problems with Gaussian measures
cites work: Information of varying cardinality
cites work: A survey of information-based complexity
full work available at URL: 0885-064x(85)90023-8
OpenAlex ID: W1999786887
description: scientific article; zbMATH DE number 3940725