Average case optimality for linear problems

J. F. Traub; G. W. Wasilkowski; H. Woźniakowski

doi:10.1016/0304-3975(84)90009-4

Average case optimality for linear problems

J. F. Traub, G. W. Wasilkowski, H. Woźniakowski

Computer Science

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

18 Scopus citations

Abstract

We introduce an average case model and define general notions of optimal algorithm and optimal information. We prove that the same algorithm and information are optimal in the worst and average cases and that adaptive information is not more powerful than non-adaptive information.

Original language	English
Pages (from-to)	1-25
Number of pages	25
Journal	Theoretical Computer Science
Volume	29
Issue number	1-2
DOIs	https://doi.org/10.1016/0304-3975(84)90009-4
State	Published - 1984

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(84)90009-4

Cite this

@article{ef1cd6b873e64ea9a327ac41518fb721,

title = "Average case optimality for linear problems",

abstract = "We introduce an average case model and define general notions of optimal algorithm and optimal information. We prove that the same algorithm and information are optimal in the worst and average cases and that adaptive information is not more powerful than non-adaptive information.",

author = "Traub, {J. F.} and Wasilkowski, {G. W.} and H. Wo{\'z}niakowski",

year = "1984",

doi = "10.1016/0304-3975(84)90009-4",

language = "English",

volume = "29",

pages = "1--25",

number = "1-2",

}

TY - JOUR

T1 - Average case optimality for linear problems

AU - Traub, J. F.

AU - Wasilkowski, G. W.

AU - Woźniakowski, H.

PY - 1984

Y1 - 1984

N2 - We introduce an average case model and define general notions of optimal algorithm and optimal information. We prove that the same algorithm and information are optimal in the worst and average cases and that adaptive information is not more powerful than non-adaptive information.

AB - We introduce an average case model and define general notions of optimal algorithm and optimal information. We prove that the same algorithm and information are optimal in the worst and average cases and that adaptive information is not more powerful than non-adaptive information.

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

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

U2 - 10.1016/0304-3975(84)90009-4

DO - 10.1016/0304-3975(84)90009-4

M3 - Article

AN - SCOPUS:0021384455

SN - 0304-3975

VL - 29

SP - 1

EP - 25

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Average case optimality for linear problems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this