Online Permutation Embedding: Optimal Stopping and Scaling Laws
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.19050
curl -X POST /api/v1/records/arxiv/2608.19050/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.19050/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'