跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20146 · v1

Evacuating from Eventually Emerging Targets on the Line

首次提交 2026-11-16 01:26
版本更新 2026-11-16 01:26
雷达观测 2026-11-17 12:06
arXiv ↗PDF ↗

摘要

We introduce and study Eventually Emerging Linear Search, an online evacuation problem on the line that, to the best of our knowledge, has not been studied before. In this problem, nn unit-speed agents with wireless communication start at the origin and search for a hidden target at location xx, where ∣x∣≥1|x|\geq1, that becomes detectable at an unknown time TT. Visiting xx before time TT reveals nothing, and the search terminates only when all agents have reached the target. We study two competitive measures. In the emergence-aware model, the target location becomes known to the offline algorithm at time TT, giving cost T+∣x∣T+|x|. In the fully-informed model, the offline algorithm knows xx from the beginning, giving cost max⁡{∣x∣,T}\max\{|x|,T\}. For one agent, the optimal competitive ratio is 99 under both measures, as in classical cow-path search. For two agents, we give an algorithm with competitive ratio 3+63+\sqrt6 under both measures, and prove it optimal within the class of origin-separated algorithms, in which each agent performs strictly expanding origin-return excursions on a fixed half-line. We also prove the unconditional lower bounds 4.354.35 and 4.384.38 for the emergence-aware and fully-informed measures, respectively. These bounds are computer-assisted; we derive finite linear programming relaxations for arbitrary algorithms and certify their infeasibility using exact rational Farkas certificates. For three agents, we prove analytically the unconditional lower bounds 3.10143.1014 and 3.28233.2823 for the emergence-aware and fully-informed measures, respectively, and introduce a geometric three-peak family. Different parameter choices give the corresponding upper bounds 4.0105994.010599 and 4.3404454.340445. These bounds lie below the corresponding two-agent lower bounds, so a third agent provably improves both measures.

作者备注:52 pages

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 01:26 · 最新观测版本

Evacuating from Eventually Emerging Targets on the Line

We introduce and study Eventually Emerging Linear Search, an online evacuation problem on the line that, to the best of our knowledge, has not been studied before. In this problem, nn unit-speed agents with wireless communication start at the origin and search for a hidden target at location xx, where ∣x∣≥1|x|\geq1, that becomes detectable at an unknown time TT. Visiting xx before time TT reveals nothing, and the search terminates only when all agents have reached the target. We study two competitive measures. In the emergence-aware model, the target location becomes known to the offline algorithm at time TT, giving cost T+∣x∣T+|x|. In the fully-informed model, the offline algorithm knows xx from the beginning, giving cost max⁡{∣x∣,T}\max\{|x|,T\}. For one agent, the optimal competitive ratio is 99 under both measures, as in classical cow-path search. For two agents, we give an algorithm with competitive ratio 3+63+\sqrt6 under both measures, and prove it optimal within the class of origin-separated algorithms, in which each agent performs strictly expanding origin-return excursions on a fixed half-line. We also prove the unconditional lower bounds 4.354.35 and 4.384.38 for the emergence-aware and fully-informed measures, respectively. These bounds are computer-assisted; we derive finite linear programming relaxations for arbitrary algorithms and certify their infeasibility using exact rational Farkas certificates. For three agents, we prove analytically the unconditional lower bounds 3.10143.1014 and 3.28233.2823 for the emergence-aware and fully-informed measures, respectively, and introduce a geometric three-peak family. Different parameter choices give the corresponding upper bounds 4.0105994.010599 and 4.3404454.340445. These bounds lie below the corresponding two-agent lower bounds, so a third agent provably improves both measures.

查看此版本解读 →查看此版本原文 ↗