{"id":"arxiv/2608.19050","url":"https://arxiv.org/abs/2608.19050","tags":["math.PR","cs.DS","math.CO"],"score":0,"title":"Online Permutation Embedding: Optimal Stopping and Scaling Laws","domain":"math.PR","source":"arxiv","authors":["Dylan J. Altschuler","Quentin Dubroff","Konstantin Tikhomirov"],"reviews":0,"subject":"math.PR","summary":"We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}