Reports

Average Case Optimality for Linear Problems

Traub, Joseph F.; Wozniakowski, Henryk; Wasilkowski, Grzegorz W.

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 nonadaptive information.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-031-82
Published Here
October 25, 2011