2015 | OriginalPaper | Chapter
Group Search on the Line
Authors : Marek Chrobak, Leszek Gąsieniec, Thomas Gorry, Russell Martin
Published in: SOFSEM 2015: Theory and Practice of Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we consider the
group search problem
, or
evacu- ation problem
, in which
k
mobile entities (
${\cal M}{\cal E}$
s) located on the line perform search for a specific destination. The
${\cal M}{\cal E}$
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
${\cal M}{\cal E}$
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 9
d
−
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
${\cal M}{\cal E}$
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
${\cal M}{\cal E}$
s, group search cannot be performed faster than in time 9
d
−
o
(
d
). We also examine the case of
k
= 2
${\cal M}{\cal E}$
s with different speeds, showing a surprising result that the bound of 9
d
can be achieved when one
${\cal M}{\cal E}$
has unit speed, and the other
${\cal M}{\cal E}$
moves with speed at least 1/3.