A randomized competitive algorithm for evaluating priced AND/OR trees

Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a μ ( T ) -competitive deterministic polynomial time algorithm, where μ ( T ) is the number of leaves that must be read, in the worst case, in order to determine the value of T. Furthermore, they proved that μ ( T ) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we take a step towards solving this problem by presenting a 5 6 μ ( T ) -competitive randomized polynomial time algorithm. This contrasts with the best known lower bound μ ( T ) / 2.

Authors

• Eduardo Sany Laber

Keywords

• Randomized algorithms
• Competitive analysis
• Function evaluation
• AND/OR trees