← 研踪 PaperTrailarXiv:2611.26135 · v1
Tight Bounds for Distance-Unbiased Sorting
首次提交 2026-11-19 21:55
版本更新 2026-11-19 21:55
雷达观测 2026-11-20 16:53
摘要
We study elitist randomized local search for sorting permutations. In this model, each iteration considers a possible exchange of two positions. The entries are exchanged if and only if they are in the wrong order. We introduce \emph{distance-unbiased} selection rules, which may choose an arbitrary distribution over exchange distances but sample uniformly among all pairs at each chosen distance. For static rules, we prove that the optimal worst-case high-probability runtime is . This establishes the asymptotic optimality of the harmonic sorter within this class and partially resolves an open question of Olesker-Taylor. We then allow the distance distribution to change either according to a predetermined schedule or adaptively using the current permutation and the entire history. Matching upper and lower bounds show that both classes have optimal runtime . Thus, scheduled adjustments of the distance distribution improve the optimal static worst-case runtime by a factor of , while full-information adaptation provides no further asymptotic improvement.
作者备注:Submitted to EvoCOP 2027
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 21:55 · 最新观测版本
Tight Bounds for Distance-Unbiased Sorting
We study elitist randomized local search for sorting permutations. In this model, each iteration considers a possible exchange of two positions. The entries are exchanged if and only if they are in the wrong order. We introduce \emph{distance-unbiased} selection rules, which may choose an arbitrary distribution over exchange distances but sample uniformly among all pairs at each chosen distance. For static rules, we prove that the optimal worst-case high-probability runtime is . This establishes the asymptotic optimality of the harmonic sorter within this class and partially resolves an open question of Olesker-Taylor. We then allow the distance distribution to change either according to a predetermined schedule or adaptively using the current permutation and the entire history. Matching upper and lower bounds show that both classes have optimal runtime . Thus, scheduled adjustments of the distance distribution improve the optimal static worst-case runtime by a factor of , while full-information adaptation provides no further asymptotic improvement.
查看此版本解读 →查看此版本原文 ↗