From directed path to linear order - the best choice problem for powers of directed path

Andrzej Grzesik, Michał Morayne, Małgorzata Sulkowska

Published 2013-08-12Version 1

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.