{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:59Z","timestamp":1787323019096,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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&lt;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 permutation. 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 gap 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.<\/jats:p>","DOI":"10.1137\/130950689","type":"journal-article","created":{"date-parts":[[2015,3,11]],"date-time":"2015-03-11T11:26:14Z","timestamp":1426073174000},"page":"500-513","source":"Crossref","is-referenced-by-count":2,"title":["From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path"],"prefix":"10.1137","volume":"29","author":[{"given":"Andrzej","family":"Grzesik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Morayne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ma\u0142gorzata","family":"Sulkowska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,11]]},"reference":[{"key":"atypb1","unstructured":"W. Feller,\n                      An introduction to probability theory and its applications, Vol.\n                      II, John Wiley and Sons, New York, 1966."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v15-1579"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/09076845X"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20466"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20192"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.02.001"},{"key":"atypb8","first-page":"153","author":"Gnedin A.V.","year":"1992","journal-title":"RI"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.06.026"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"W. Kaz\u0301mierczak,\n                      The best choice problem for posets; colored complete binary trees\n                      , J. Combin. Optim. (2014).","DOI":"10.1007\/s10878-014-9705-5"},{"key":"atypb12","first-page":"439","author":"Kozik J.","year":"2010","journal-title":"Vienna"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104440596"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.2307\/2985407"},{"key":"atypb15","first-page":"39","author":"Kumar R.","year":"2011","journal-title":"New York"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00091-5"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00053-X"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.10.023"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.08.001"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2012.04.001"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"W. Stadje,\n                      Efficient stopping of a random series of partially ordered points\n                      , In Proceedings of the III International Conference on Multiple Criteria Decision Making, Ko\u0308nigswinter, 1979, Lecture Notes in Econom. Math. Systems 177, Springer, Berlin, 1980.","DOI":"10.1007\/978-3-642-48782-8_30"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130950689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:15Z","timestamp":1787319435000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130950689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130950689"],"URL":"https:\/\/doi.org\/10.1137\/130950689","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}