English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We examine the evolution of the best choice algorithm and the probability ofits success from a directed path to the linear order of the same cardinalitythrough $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 toa selector in some random order. At any time the selector can see the graphinduced by the vertices that have already come. The selector's aim is to chooseonline the maximal vertex (i.e. the vertex with no outgoing edges). It is shownthat the probability of success $p_n$ for the optimal algorithm for the $k$thpower of a directed path satisfies $p_n = \Theta(n^{-1/(k+1)})$. We alsoconsider the case when the selector knows the distance in the underlying pathbetween each two vertices that are joined by an edge in the induced graph. Anoptimal algorithm for this choice problem is presented. The exact probabilityof success when using this algorithm is given.

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