{"id":"arxiv/2606.32015","url":"https://arxiv.org/abs/2606.32015","tags":["cs.DS","math.PR"],"score":0,"title":"The online monotone array completion problem","domain":"cs.DS","source":"arxiv","authors":["Vishesh Jain","Dylan King","Clayton Mizgerd"],"reviews":0,"subject":"cs.DS","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-30","reactions":{}}