Group Search on the Line



Chrobak, Marek, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Gorry, Thomas and Martin, Russell ORCID: 0000-0002-7043-503X
(2015) Group Search on the Line. In: 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), 2015-1-24 - 2015-1-29, Pec pod Snezkou, Czech Republic.

[img] Text
paper_87.pdf - Author Accepted Manuscript

Download (144kB)

Abstract

In this paper we consider the group search problem, or evacuation problem, in which k mobile entities (Mεs) located on the line perform search for a specific destination. The Mεs are initially placed at the same origin on the line L and the target is located at an unknown distance d, either to the left or to the right from the origin. All Mεs must simultaneously occupy the destination, and the goal is to minimize the time necessary for this to happen. The problem with k = 1 is known as the cow-path problem, and the time required for this problem is known to be 9d - o(d) in the worst case (when the cow moves at unit speed); it is also known that this is the case for k ≥ 1 unit-speed Mεs. In this paper we present a clear argument for this claim by showing a rather counter-intuitive result. Namely, independent of the number of Mεs, group search cannot be performed faster than in time 9d - o(d). We also examine the case of k = 2 Mεs with different speeds, showing a surprising result that the bound of 9d can be achieved when one Mε has unit speed, and the other Mε moves with speed at least 1/3.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: evacuation, group search, mobile entity
Depositing User: Symplectic Admin
Date Deposited: 25 Aug 2016 07:38
Last Modified: 19 Jan 2023 07:32
DOI: 10.1007/978-3-662-46078-8_14
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3003021