From directed path to linear order - the best choice problem for powers of directed path
Preprint
Abstract
We examine the evolution of the best choice algorithm and the probability of its success from a directed path to the linear order of the same cardinality through $k$th powers of a directed path, $1 \leq k < n$. The vertices of a $k$th power of a directed path of a known length $n$ are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already come. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). It is shown that the probability of success $p_n$ for the optimal algorithm for the $k$th power of a directed path satisfies $p_n = \Theta(n^{-1/(k+1)})$. We also consider the case when the selector knows the distance in the underlying path between each two vertices that are joined by an edge in the induced graph. An optimal algorithm for this choice problem is presented. The exact probability of success when using this algorithm is given.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The best choice problem for posets; colored complete binary treesJournal of Combinatorial Optimization, 2014
- An efficient algorithm for stopping on a sink in a directed graphOperations Research Letters, 2013
- The secretary problem on an unknown posetRandom Structures & Algorithms, 2012
- The best choice problem for upward directed graphsDiscrete Optimization, 2012
- Optimal stopping in a search for a vertex with full degree in a random graphDiscrete Applied Mathematics, 2012
- How to Choose the Best TwinsSIAM Journal on Discrete Mathematics, 2012
- Gusein-Zade problem for directed pathDiscrete Optimization, 2010
- On a universal best choice algorithm for partially ordered setsRandom Structures & Algorithms, 2007
- The best-choice problem for partially ordered objectsOperations Research Letters, 1999
- Partial-order analogue of the secretary problem the binary tree caseDiscrete Mathematics, 1998