Seminário de Teoria da Computação

       
           A General Approach for Querying Priced Information

                    Eduardo S. Laber -- PUC-RJ

                  Sexta-feira, 15 de abril de 2005 

                       Sala 85  14:00hs

Abstract: In this talk, we focus on competitive function evaluation in
the context of computing with priced information. A function $f$ is
given together with a cost $c_x$ for each variable $x$ of $f$.  The
cost $c_x$ has to be paid to read the value of $x$. The problem is to
design algorithms that query the values of the variables sequentially
in order to compute the function while trying to minimize the total
cost incurred. Competitive analysis is employed to evaluate the
performance of the algorithms. We describe a novel approach for
devising efficient algorithms in this setting. We apply our approach
to several classes of functions which have been studied in the
literature of computing with priced information.  , e.g., monotone
boolean functions, game trees, selection of the minimum.  In all cases
considered, our approach provides optimal algorithms.