From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path

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

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2015-01, Vol.29 (1), p.500-513
Main Authors: Grzesik, Andrzej, Morayne, Michał, Sulkowska, Małgorzata
Format: Article
Language:English
Subjects:
Algorithms
Evolution
Graph theory
Graphs
Mathematical analysis
Online
Optimization
Permutations
Selectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0895-4801
1095-7146
DOI:10.1137/130950689