Surface light-induced changes in thin polymer films
Andrew Skumanich
SPIE Optics Quebec 1993
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest "proof for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework and construct, for every AND/OR tree, a set of prices that satisfies a very strong type of equilibrium property. © 2002 Elsevier science (USA).
Andrew Skumanich
SPIE Optics Quebec 1993
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994