Search and Rescue on the Ring
International Journal of Foundations of Computer Science · 13.05.2026 · 1-19
DOI: 10.1142/s0129054126490055 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 13.05.2026. Verfasst von Nianhan Guo und 4 weiteren Autor:innen. Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Zhejiang Province.
Abstract (Originalsprache)
This paper studies the online problem of search and rescue on a (unit) ring. Assuming that an object is located somewhere unknown on the ring, we aim to find the object and deliver it to a designated destination by one or more mobile agents, so that the total time spent is minimized. The agent(s) can only move along the ring, and is initially located a distance of [Formula: see text] away from the destination. For single-agent search and rescue, we present an optimal deterministic algorithm with a competitive ratio of [Formula: see text], and as well as randomized algorithms corresponding to [Formula: see text] and [Formula: see text], whose expected competitive ratios can be accurately computed by non-linear programming. For the two-agent search and rescue, we propose deterministic algorithms with competition ratios depending on whether the agents can communicate through the radios.
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Zhejiang Province
Zitieren
APA
Guo, N., Wang, X., Zhang, A., Chen, Y., & Chen, G. (2026). Search and Rescue on the Ring. International Journal of Foundations of Computer Science, 1-19. https://doi.org/10.1142/s0129054126490055
Vancouver
Guo N, Wang X, Zhang A, Chen Y, Chen G. Search and Rescue on the Ring. International Journal of Foundations of Computer Science. 2026:1-19. doi:10.1142/s0129054126490055
BibTeX
@article{Guo2026,
author = {Guo, Nianhan and Wang, Xing and Zhang, An and Chen, Yong and Chen, Guangting},
title = {Search and Rescue on the Ring},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--19},
doi = {10.1142/s0129054126490055}
}
EUVIMED