The algorithm designer versus nature: A game-theoretic approach to information-based complexity |
| |
Institution: | Department of Mathematics and Computer Studies, Lake Forest College, Lake Forest, Illinois 60045, USA |
| |
Abstract: | A new setting for analyzing problems in information-based complexity is formulated and discussed. By using concepts from two-person zero-sum game theory, a randomized setting results from defining the nth minimal radius as an infimum over “mixed” strategies of information operators and algorithms. After presenting an example, some general results are developed on the randomized radius and its relationship to average and worst case radii. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|