Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2000-08 July 2000

Abstract

In this paper we introduce a new class of search problem which we call `alternating search'. Two searchers starting at given points in different search regions, who can move alternately with speed one, or (as a limiting case) simultaneously with combined speed one, seek to find (reach) an object in least expected time. The hidden object is stationary and its location is given by a known distribution over the union of the two search regions. An important special case is the `Double Linear Search Problem' in which both search regions are infinite lines, and which has been shown to be equivalent to the `Asymmetric Rendezvous Search Problem on the Line' (ARSPL). The general results proved here are applied in a concurrent paper of Alpern and Beck to prove that the strategy conjectured by Baston and Gal to be optimal for the convex ARSPL is indeed optimal. Our general results are concerned with determining the method of interleaving two given distributions so as to minimize the first moment of the resulting distribution.

A compressed (gzip) PostScript file (101 kB) with the contents of this report (sorry, without figures) can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-08, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.