{"ID":2845812,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03485","arxiv_id":"2511.03485","title":"Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms","abstract":"This paper studies the online scheduling problem of minimizing total flow time for $n$ jobs on $m$ identical machines. A classical $Ω(n)$ lower bound shows that no deterministic single-machine algorithm can beat the trivial greedy, even when $n$ is known in advance. However, this barrier is specific to deterministic algorithms on a single machine, leaving open what randomization, multiple machines, or the kill-and-restart capability can achieve. We give a nearly complete answer. For randomized non-preemptive algorithms, we establish a tight $Θ(\\sqrt{n/m})$ competitive ratio, which also improves the best offline approximation to $O(\\sqrt{n/m})$. For deterministic non-preemptive algorithms on multiple machines, we prove an $O(n/m^2 + \\sqrt{n/m}\\log m)$ upper bound and an $Ω(n/m^2 + \\sqrt{n/m})$ lower bound. In the kill-and-restart model, we reveal a sharp transition for deterministic algorithms: $Ω(n/\\log n)$ for $m = 1$ versus $Θ(\\sqrt{n/m})$ for $m \\ge 2$; the latter matches the optimal randomized ratio, and we further show that randomization provides no additional power in this model. We also investigate the setting where $n$ is unknown. We prove that no randomized non-preemptive algorithm achieves $o(n)$ on one machine or $o(n/m^2 + \\sqrt{n/m})$ on $m$ machines. In contrast, our kill-and-restart algorithm achieves $O(n^α/\\sqrt{m})$ for $m \\ge 2$, where $α= (\\sqrt{5}-1)/2$, breaking the trivial bound without knowledge of $n$.","short_abstract":"This paper studies the online scheduling problem of minimizing total flow time for $n$ jobs on $m$ identical machines. A classical $Ω(n)$ lower bound shows that no deterministic single-machine algorithm can beat the trivial greedy, even when $n$ is known in advance. However, this barrier is specific to deterministic al...","url_abs":"https://arxiv.org/abs/2511.03485","url_pdf":"https://arxiv.org/pdf/2511.03485v3","authors":"[\"Yutong Geng\",\"Enze Sun\",\"Zonghan Yang\",\"Yuhao Zhang\"]","published":"2025-11-05T14:11:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}