-----------------------------------------------------------------------
TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar
-----------------------------------------------------------------------

Title:   Towards Efficient Search Engines for Mobile Devices 
Speaker: Grzegorz Malewicz 

Place:   NE43-308
Time:    1-2:30pm
Date:    Nov. 08, 2002

Abstract:

A prevailing feature of mobile telephony systems is that the cell
where a mobile user is located may be unknown. Therefore when the
system is to establish a call between users it needs to search, or
page, all the cells that it suspects the users are located in, to find
the cells where the users currently reside. The search consumes
expensive wireless links and so it is desirable to develop search
techniques that page as few cells as possible.

We consider a cellular system with $c$ cells and $m$ mobile users
where the location of the users is uncertain as given by $m$
probability distribution vectors. The search operation lasts a given
number of {\em rounds}. In each round the system may page an arbitrary
subset of cells to find out which users are located there. In this
setting the problem of finding one user with minimum expected number
of cells paged is known to be solved optimally in polynomial time. In
this work we address the problem of finding several users with the
same optimization goal. We show that the problem is NP-hard and
provide a $\frac{e}{e-1}$ approximation solution.

This research is joint work with Amotz Bar-Noy published at PODC'02.
During the talk we will report on some of our recent unpublished
results and on future directions.

-----------------------------------------------------------------------