Graph-Theoretic Generalization of the Best-Choice Problem: Randomized Analysis of a Simple Effective Algorithm for k-ary Trees
Description We consider the following on-line decision problem. The vertices of a graph which is a complete rooted directed k-ary tree are being observed one by one in some random order by a selector...