1982 Reports
Average Case Optimality for Linear Problems
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
-
cucs-031-82.pdf application/pdf 1010 KB Download File
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