The online monotone array completion problem
Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $\mathrm{Unif}[0,1]$ and must either discard it or place it irrevocably into an empty position of the array, while preserving the constraint that the occupied entries are non-decreasing from left to right. Among all possible strategies, what is the optimal expected time required to fill the array? Let $v_n$ denote this optimal expected completion time. Our main result determines $v_n$ up to lower-order terms: \[ v_n=\left(\frac12+o(1)\right)n\log n.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.32015
curl -X POST /api/v1/records/arxiv/2606.32015/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.32015/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'