A randomized competitive algorithm for evaluating priced AND/OR trees

DOI10.1016/J.TCS.2008.03.033MaRDI QIDQ935154zbMATH OpenOpenAlexFDO

Authors Eduardo S. Laber

Publication date 31 July 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.03.033

zbMATH Keywords

randomized algorithmscompetitive analysisfunction evaluationAND/OR trees

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• STACS 2004
• On the competitive ratio of evaluating priced functions
• Uniqueness of optimal randomized algorithms for balanced AND-OR trees
• Algorithms – ESA 2005
• A new strategy for querying priced information

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1947429 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• An analysis of alpha-beta pruning
• LATIN 2004: Theoretical Informatics
• Lower bounds on probabilistic linear decision trees
• On the Optimality of Randomized $\alpha$-$\beta$ Search
• Optimal Search on Some Game Trees
• Query strategies for priced information
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Cited in

(6)

• Revisiting the complexity of and/or graph solution
• And/or-convexity: a graph convexity based on processes and deadlock models
• Optimal randomized algorithms of weakly-balanced multi-branching AND-OR trees
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• STACS 2004
• Uniqueness of optimal randomized algorithms for balanced AND-OR trees

This page was built for publication: A randomized competitive algorithm for evaluating priced AND/OR trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q935154)