The best choice problem for posets; colored complete binary trees
Wojciech Kaźmierczak · Journal of Combinatorial Optimization · 2014
We consider the poset version of the secretary problem for rooted complete binary trees of a given length n where the $$2^{n-a}$$ complete binary trees whose roots are at the level $$a+1$$ (counting from the leaves) are colored with different colors visible to the selector and the vertices above level $$a+1$$ are colored in a natural way according to the vertices below them that came earlier. We find an optimal stopping time for two-colored trees and near optimal strategies for more than two colors.