1. The best choice problem for upward directed graphs
- Author
-
Małgorzata Sulkowska
- Subjects
Discrete mathematics ,Best choice ,Generalization ,Directed graph ,Applied Mathematics ,Secretary problem ,Theoretical Computer Science ,Combinatorics ,Computational Theory and Mathematics ,Universal algorithm ,Bounded function ,Path (graph theory) ,Graph (abstract data type) ,Constant (mathematics) ,Maximal element ,Mathematics - Abstract
We consider a generalization of the best choice problem to upward directed graphs. We describe a strategy for choosing a maximal element (i.e., an element with no outgoing edges) when a selector knows in advance only the number n of vertices of the graph. We show that, as long as the number of elements dominated directly by the maximal ones is not greater than c 1 n for some positive constant c 1 and the indegree of remaining vertices is bounded by a constant D , the probability p n of the right choice according to our strategy satisfies lim inf n → ∞ p n n ≥ δ > 0 , where δ is a constant depending on c 1 and D .
- Published
- 2012