EUVIMEDEUVIMED entdecken
Crossref

Search and Rescue on the Ring

Nianhan Guo, Xing Wang, An Zhang, Yong Chen, Guangting Chen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →