Average case optimality

G. W. Wasilkowski

doi:10.1016/0885-064X(85)90023-8

Average case optimality

G. W. Wasilkowski

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	107-117
Number of pages	11
Journal	Journal of Complexity
Volume	1
Issue number	1
DOIs	https://doi.org/10.1016/0885-064X(85)90023-8
State	Published - Oct 1985

Bibliographical note

Funding Information:
* Presented at the Symposium on Complexity of Approximately Solved Problems, April 17, 1985. ‘This research was supported in part by the National Science Foundation under Grant JXR-82-14322.

ASJC Scopus subject areas

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
Mathematics (all)
Control and Optimization
Applied Mathematics

Access to Document

10.1016/0885-064X(85)90023-8

Cite this

@article{842bdb6af83b47969863ea5569c9f3bb,

title = "Average case optimality",

abstract = "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.",

author = "Wasilkowski, {G. W.}",

note = "Funding Information: * Presented at the Symposium on Complexity of Approximately Solved Problems, April 17, 1985. {\textquoteleft}This research was supported in part by the National Science Foundation under Grant JXR-82-14322.",

year = "1985",

month = oct,

doi = "10.1016/0885-064X(85)90023-8",

language = "English",

volume = "1",

pages = "107--117",

number = "1",

}

TY - JOUR

T1 - Average case optimality

AU - Wasilkowski, G. W.

N1 - Funding Information: * Presented at the Symposium on Complexity of Approximately Solved Problems, April 17, 1985. ‘This research was supported in part by the National Science Foundation under Grant JXR-82-14322.

PY - 1985/10

Y1 - 1985/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=46549096797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46549096797&partnerID=8YFLogxK

U2 - 10.1016/0885-064X(85)90023-8

DO - 10.1016/0885-064X(85)90023-8

M3 - Article

AN - SCOPUS:46549096797

VL - 1

SP - 107

EP - 117

IS - 1

ER -

Average case optimality

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this