Establishing wireless conference calls under delay constraints.
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 may need 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 cellular systems with c cells and m mobile users roaming among the cells. The location of the users is uncertain as given by m probability distribution vectors. Whenever the system needs to find specific users, it conducts a search operation lasting some number of rounds (the delay constraint). In each round, the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.In this paper we address the problem of finding several users with the same optimization goal. This task is motivated by the problem of establishing a conference call between mobile users. We first show that the problem is NP-hard. Then we prove that a natural heuristic is an e/(e - 1 )-approximation solution.
INTRODUCTION
In the last decade, we have witnessed two trends: increasing
availability of people and increasing availability of infor-
mation. Mobile telephony systems make it possible to talk
with people even if they are not residing in predetermined
locations (as is the case with conventional phone systems).
Internet search engines allow users to accurately and eciently
access information stored on websites that have xed
location. When information is stored on mobile devices and
needs to be retrieved new challenges occur. An intrinsic feature
of current mobile telephony systems is that location of
the devices is uncertain. A challenge here is to design search
algorithms that e-ciently retrieve information given limited
knowledge about its location.
In this paper we focus on search techniques that are motivated
by the problem of establishing a conference call in a
wireless phone system. Our goal is to nd a given collection
of mobile devices inside a wireless system so as to minimize
the usage of expensive wireless links and control the amount
of time spent on the search.
1.1 Background and motivation
Our problem of establishing wireless conference calls is
motivated by the state-of-the-art of wireless technology. Currently
deployed wireless personal communication systems
are composed of a set of base stations connected by a wired
backbone network. The range of radio transmission of a base
station determines an area called a cell. Each mobile device
that roams inside the system communicates with other
devices (mobile or stationary) through base stations using
signals. When a mobile device is within the range of
a base station the terminal is said to be located in the cell
determined by the base station.
One of the main components of a wireless system is a location
management service [2]. Its goal is to track the locations
of devices that are needed in order to establish calls. In some
cases the system knows the current location of a mobile device
and then the system does not need to search for the
device to establish a call. This occurs, for example, when
the device is participating in an ongoing call and therefore
is repeatedly communicating with base stations. However in
general the location of a device may be unknown for example
because the device has been switched o by the user in
order to preserve battery power. This gives rise to the need
of locating mobile devices which is the aim of a location
management service.
The tracking problem exhibits an inherent tradeo between
the load imposed on the system by devices reporting
their location and the load imposed when the system
searches for devices (see for example [5]). To illustrate, let
us assume that each terminal reports its location by sending
a message over a wireless link to the base station every time
it enters a new cell. This means that the system has up-
to-date information about terminal location and when call
is to be established the system does not need to search for
a device. Assume on the other hand that terminals never
report their location. Then when the system is to establish
a call with a terminal it must nd the cell where the
terminal is currently located. Since the terminal is mobile
the system may need to search all cells in the system, which
is done by broadcasting over wireless links, or paging, from
base stations.
Several factors aect the total cost incurred by the system
due to reporting and paging. Reporting location consumes
limited battery power of terminals. In addition the wireless
links used for reporting are expensive and may become congested
by the volume of update tra-c especially when terminals
are highly mobile and frequently cross the boundaries
between cells. Paging also may consume scarce wireless links
specically when large number of cells needs to be paged to
nd the device and the incoming call frequency is large. An
eective and e-cient location management system needs to
achieve a balance between reporting and paging depending
on these factors.
Presently major wireless systems use a simple technique
to balance between reporting and paging tra-c. In GSM
MAP [11] (used in Europe) and IS-41 [10] (used in North
America) standards the set of all cells is partitioned into
subsets called location areas each containing many cells (but
only a fraction of all cells in the system). Any cell broadcasts
the identier of its location area on a special radio channel.
When a mobile terminal nds out that it has moved from a
cell to a cell belonging to a dierent location area it sends a
wireless signal (reports) to the base station of the later cell.
This information is persisted in a database connected to
the backbone network, that stores the most recently visited
location area for each terminal. When a call to a mobile
terminal is to be established the system broadcasts (pages)
radio signals in parallel from all base stations in the location
area asking the terminal to respond. This technique reduces
the number of cells paged when a call is to be established
because only the cells belonging to a location area are paged.
However this comes at the cost that devices must report
whenever they cross boundaries between location areas. The
choice of location areas aects the reporting tra-c (e.g., [1,
6]).
A technique has been developed [13, 18, 19] to reduce
the number of cells paged inside a location area during the
search for a single mobile device at the cost of increased
amount of time needed for paging. The technique considers
a model of a location area with c cells where the probability
distribution of the device across the cells is given. (There
are several methods for approximating the distribution; see
[17, 18] for examples). Here an arbitrary subset of cells of
the location area can be paged in parallel in unit time to see
if the device is located there. Also paging can be performed
for d  c units of time. Paging is carried out according to a
d-round strategy, where in each round i a subset S i
of cells is paged until the device is found. Authors
show how to e-ciently nd a strategy that has at most d
rounds and that minimizes expected number of cells paged.
For example if the device is uniformly distributed across all
c cells, c even, and we have at most 2 units of time for paging
then the best paging strategy is to page half of the cells in
the rst round and when the device is not found in these cells
then page the other half in the second round. This gives 3
expected number of cells paged (a 1
improvement over the
technique specied by GSM MAP and IS-41 standards).
It is very interesting to investigate how to generalize the
technique to nd more than one device. This is motivated by
the problem of establishing a wireless conference call. The
goal is to nd a given collection of mobile devices inside a
wireless system so as to minimize the usage of expensive
wireless links and control the amount of time spent on the
search.
1.2 Model and problem statement
Assume a model with c cells and m mobile devices. We
assign all the devices to cells by selecting a cell j for a device
independently from other devices. We
assume that each probability is positive and that p i;1
In this setting we can probe (or page) an
arbitrary group of cells in a unit of time and detect which
devices are located there. We also assume that we can aord
to perform probing for d units of time.
The goal is to develop e-cient algorithms that can nd all
the devices within at most d units of time and that page the
least expected number of cells. In general one can consider
two types of algorithms: oblivious and adaptive. Oblivious
algorithms page, in each unit of time, a predetermined sub-set
of cells. Adaptive algorithms decide which cells to page
during a unit of time based on the devices that have been
found so far. Each type has its advantages. Adaptive algorithms
may achieve lower expected number of cells paged
to nd all terminals. Oblivious algorithms have very low
computational cost during the search process. In this work
we focus on oblivious algorithms.
Specically, a strategy is a sequence of nonempty
sets that partition is called the
length of the strategy. We call each set a group. For a
given strategy cells are paged in rounds such that in round
t, all cells in the group Sr are paged. Cells
are not paged when all mobile devices have been
found i.e., if and only if r is the smallest round number for
which all mobile devices are located in cells
For each strategy we can nd the expected number of cells
paged until all mobile devices have been found. We call this
number the expected paging of the strategy. We seek a strategy
that minimizes this expectation. We call the problem
the Conference Call problem.
Conference Call
Instance: Number of mobile devices m  1, number of cells
c  1, positive probabilities p i;j of nding mobile device i in
cell j such that for all i,
number of rounds d, 1  d  c.
Objective: Find a strategy that minimizes expected paging
for all strategies of length at most d.
For example when the problem is trivial since all
the cells must be paged in the rst and only round. The
problem becomes interesting when because we are
looking for a subset of the cells to be paged in the rst
round to minimize the expected number of cells paged until
all devices have been found (if they are not located in the
cells paged in the rst round then we need to page all the
remaining cells). When c, we are looking for a permutation
of the cells that dictates the sequence in which cells are
paged that minimizes the expected number of cells paged
until all devices have been found.
1.3 Contributions
The problem of searching for one device known
[13, 18, 19] to be solvable optimally for any d in polynomial
time using a dynamic programming algorithm. In this paper
we address the general problem of searching for m  1
devices. Our contributions are as follows:
Complexity of the problem. We rst show that the Conference
Call problem is NP-hard by a nontrivial reduction
from a special type of the Partition problem. We
also show that the special case of the Conference Call
problem for two users and two rounds
is NP-hard. This appears in Theorem 3.2. Our result
establishes a threshold: the problem is easy when
2.
Constant factor approximation. We present a very simple
and natural heuristic. In this heuristic we sequence
the cells in a non-decreasing order of expected number
of devices located in each cell and use dynamic programming
to nd the partition of this sequence into d
subsequences. We show that the expected number of
cells paged by this heuristic is at most e
times the
minimal number of cells paged by any strategy. This
appears in Theorem 5.5. We also show a lower bound
of 320
317 on the performance ratio of our heuristic.
1.4 Paper organization
The rest of the paper is structured as follows. In Section 2,
we present some preliminaries. In Section 3, we prove that
the problem is NP-hard. In Section 4, we study a special case
of the problem to demonstrate techniques used in showing
a constant factor approximation given in Section 5. Finally,
in Section 6, we discuss future work and related work.
2. PRELIMINARIES
We show that the Conference Call problem is a combinatorial
optimization problem and restate some existing results
from convex optimization that we use throughout. In the
lemma below we show how to nd the expected paging for
a strategy.
Lemma 2.1. Let be a strategy. Then the expected
number of cells paged until all mobile devices are
found is
Y
j2Lr
Proof. The search lasts exactly r rounds whenever not
all mobile devices are found in rounds
are found on or before round r. Let Fr be the event that
all mobile devices are found on or before round r. Observe
that by independence Pr [Fr
Hence
Pr [paging lasts exactly r
Since if paging stops in round r we page jS1
cells, the expected number of cells paged until all mobile
devices are found is
which completes the proof.
It can be seen that for any strategy of length t 1 < c there
exists a strategy of length t with strictly lower expected
paging. Thus, among all strategies of length at most d, a
strategy that minimizes expected paging must have length
d.
Now we restate some basic notions and properties from
the theory of multidimensional convex optimization [20] and
linear algebra [16] that we use throughout. A subset D of
space R k is convex if for any two points x and y in D the
segment xy is contained in D. That is x
for all x; y 2 D,  2 [0; 1]. For a convex set D, a function
R is strictly convex if for any x and y in D and  2
(0; 1) we have f
matrix H of size k by k over R is positive denite if for any
We report a standard fact
that characterizes strict convexity of a function in terms of
its Hessian { the matrix of second derivatives (see [20] for a
proof and more discussion).
Theorem 2.2 ([20]). Let D be an open convex set in
R k . Suppose that a dierentiable function f : D ! R has
continuous second partial derivatives in the set D. Let the
Hessian H(x) be positive denite for every point x 2 D.
Then f is strictly convex.
Using the above theorem it is strightforward to show that
the maximum of a strictly convex function are attained at
the boundary of the domain as presented in the next lemma.
Lemma 2.3. Let f : D ! R be a strictly convex and continuous
function dened over an open, convex and bounded
subset D  R k , and let H be a closed subset of D. Then the
maximum of f on H is achieved at a point that belongs to
the boundary of H.
3. COMPLEXITY OF THE PROBLEM
In this section we show that the Conference Call problem
is NP-hard. Specically, we give a reduction of a variation
of the Partition problem to the Conference Call problem.
This variation is dened next.
Quasipartition
Instance: List of non-negative sizes
divisible by 3.
Objective: Decide if there is a set of indices I of cardinality3 c such that
x=2I sx .
This problem is NP-complete by a simple reduction from
a Partition problem presented by Garey and Johnson [12]
on page 223. We use the Quasipartition problem to show
NP-hardness of the Conference Call problem. The following
technical lemma that analyzes extrema of a function is used
in the proof.
Lemma 3.1. For any c  1 the function f : [0; 1]  [0; c]
dened as
(y x)
achieves the global maximum at a single point of the domain
Proof. Let us extend the domain of f to the set
cg. The function f is
continuous over closed and bounded domain D so it achieves
maxima either in the interior or at the boundary of D.
Let us focus on the interior rst. Observe that @f
if and only if
4c , so an extremum in the interior
can be achieved only when this condition holds. The rst
derivative of the function f( 3y
or Thus if there is extremum in the interior it is for
3 c, where the function achieves the value
Now let us consider the values of the function at the
boundary. If
@y is zero only when
for the part of boundary where the function achieves
values strictly smaller than f( 1
3 c). Finally if
c > 0, and so the maximum is achieved
when which cases the function has
non-positive values c and 0 respectively.
Thus the function f dened for a smaller domain 0  x
achieves the global maximum at a single point
Theorem 3.2. The Conference Call problem is NP-hard.
Proof. We show how to transform the Quasipartition
problem to the Conference Call problem.
sc be any list of non-negative sizes such that
c is divisible by 3, and let . If there exist
i such that s there is no partition. For the
remainder of the proof assume that s i < S, for all i. We
dene an instance of the Conference Call problem by taking
2. Since there are only two mobile
devices in this instance for clarity we denote the probabilities
that mobile devices are located in cell i by p i and q i
respectively. Let the probabilities p i and q i be dened as
, for 1  i  c.
Note that the probabilities are positive, that
and that the size of the instance of the Conference
Call problem is polynomial in the size of the instance of the
Quasipartition problem. We show that the Quasipartition
problem for the sequence S has an answer if and only if we
can answer whether the minimal expected paging for the
probabilities achieve a certain value dened below.
Before we proceed with the proof, we note a lower bound
on the value of expected paging for the instance
. Take any strategy and let I  [c],
y, be the set of cells paged in the rst round. By
Lemma 2.1 the expected paging for this strategy is
y
Let us denote
S by x, and observe that 0  x  1.
Consequently by Lemma 3.1 the expected number of cells
paged until all mobile devices are found is bounded from
below by
Suppose that P is a partition of size 2
3 c of the sequence S.
Then
so a strategy that pages cells P
in the rst round, and cells [c] n P in the second round has
expected paging equal to LB. Moreover, by Lemma 3.1, this
is the smallest value possible, so the answer to the instance
of the Conference Call is a strategy with expected paging
equal to LB.
Suppose that the answer to the instance of the Conference
Call problem is a strategy with expected paging equal to LB.
Let P be the set of cells paged in the rst round. Observe
that the cardinality of P must be 2
3 c because otherwise by
Lemma 3.1 the expected paging of the strategy would be
strictly grater than LB. For the same reasons
must be 1=2. Thus P is a partition of size 2
3 c of the sequence
S.
A special case of the Conference Call problem for
has been studied [13, 18, 19]. It was shown that it is in P. In
addition we can show (by slightly extending the argument
presented in the above theorem) that all restrictions of the
Conference Call problem to xed m  2 and are NP-hard
[7]. By further extending the argument, we believe that
the NP-hardness result can be shown for any xed m  2
and xed d  2 [7].
4. APPROXIMATION OF THE SPECIAL
For clarity of presentation, before we show a general approximation
result, we discuss a special case of the Conference
Call problem with two mobile devices and maximum
delay of two. From Theorem 3.2 we know this special case
is NP-hard. Here we show that there is a 4
3 approximation
solution that can be found in O(c) time and O(1) space.
First we show two simple propositions.
Proposition 4.1. Let 1  x  2, and variables a i and
Proof. Notice that by decreasing some a i the value of
the product (a1 can only be reduced. Thus
it is enough to bound the product from below with the
additional constraint
and we can
rewrite this expression as . By the
assumption that a2 + b2  1 we have that v  1, and by the
assumptions that
we have that
that for the domain x 1  v  1, the expression (x v) v
treated as a function of v is minimized at the boundary of
the domain when This yields a
lower bound of x 1.
Proposition 4.2. Let 0 < s  c and 1  x  2, then
Proof. Since @ 2
> 0, the function is a strictly convex function of x, and so it
is bounded from above by the greater of the values achieved
2. For its value is c s 4
0, and for its value is c 4
Thus the function is bounded from above by 0, and the result
follows.
Suppose that S1 ; S2 is a strategy that minimizes expected
paging among all strategies of length 2. We do not know
how to nd this strategy, but despite this let us assume that
we know jS1 us pick s1 cells which maximize
the expected number of devices located in the cells i.e., for
any cell j in T1 and any cell j 0 not in T1 we have p1;j
. Then the following lemma shows that
the strategy desired approximation, where
Lemma 4.3. EPT =EPS  4=3 :
Proof. Recall that by the selection of the strategy
the set contains cells j that maximize the sum p1;j +p2;j .
We divide the cells in S1 [
B. For each mobile device i we
dene a i to be the probability that the device is in the cells
A i.e., a
Similarly we dene b
and c
By the theorem of the arithmetic and geometric means
[14] we have
2. Recall that for each device i we have
consequently a 1. By the choice
of we have that
We divide the analysis of the approximation ratio into
two cases. If x < 1 then we bound the probability that all
devices are found by the strategy in the rst round
by 0. (Recall that s1 is the number of cells paged in the rst
round). Thus
c c 1= 4
For the second case assume that 1  x  2. By Proposition
4.1 we can bound the ratio as
It remains to show that the enumerator is bounded from
above by 4
3 times the denominator. But this follows from
Proposition 4.2, which completes the proof.
Note that we do not need to know the size of S1 because we
can aord to evaluate expected paging of a strategy
constructed for evaluate it for
on until pick the strategy that minimizes
expected paging. Thus we can nd a strategy that is a 4approximation without the knowledge of the size of the set
of cells paged in the rst round by a two-round strategy that
minimizes expected paging.
5. CONSTANTFACTORAPPROXIMATION
This section is devoted to generalizing the ideas given in
the previous section. For this purpose we employ techniques
from multidimensional convex optimization and dynamic
programming. Specically we show an e
{approximation
algorithm for the Conference Call problem. Our algorithm
uses a very simple heuristic. Intuitively a good paging strategy
rst pages cells that have large chances of nding all mobile
devices in the cells. To realize this intuition we sequence
cells in a non-increasing order of the sum of probabilities of
nding mobile devices in the cells. In particular the rst cell
in the sequence is a cell j that maximizes
and the last cell in the sequence is a cell j that minimizes
. Then we nd a certain strategy that pages,
in each round, consecutive cells from the sequence and show
that this strategy is a desired approximation. The proof
of the correctness of the approximation algorithm has two
steps. We consider a family of all strategies of length d that
page cells according to the sequence. First we show that
there exists a strategy T in this family that has the value
of expected paging by at most e
greater than the
minimal value of expected paging for any strategy (not necessarily
from the family). However the strategy T needs to
probe, in each round, the same number of cells as a strategy
S that minimizes expected paging. Since we do not know
the sizes of groups for the strategy S we cannot e-ciently
nd T! In the second step we show that with the help of dynamic
programming we can e-ciently nd a strategy G in
the family that minimizes expected paging across all strategies
in the family. Thus the strategy G has expected paging
at most equal to expected paging of the strategy T, which
completes the proof. In the following two sections we present
the details of this argument.
In the remainder of the section we assume that all cells
are ordered so that for all 1
. We consider a family F of all strategies
Sd such that any group S j , j  2, contains cells
greater than all preceding groups in the strategy i.e., for all
5.1 Existence of approximate solution
In this section we demonstrate that the family F contains
a strategy T that has the expected number of cells paged until
all mobile devices are found larger by at most the factor of
e
than the expected paging of a strategy of length d that
minimizes the expectation. The key idea behind the proof is
to observe that if an optimal strategy yields small chances of
nding all mobile devices until a round then the strategy T
is trivially good enough, while when these chances are high
then the strategy T must also have high chance of nding
all mobile devices.
For the analysis of performance of our heuristic we need
two technical inequalities, which we show next. These inequalities
generalize Proposition 4.1 and Proposition 4.2 given
in the previous section. We prove the more general facts using
techniques from multidimensional convex optimization.
Lemma 5.1. Let m  2, m 1  x  m, and variables a i
and b i satisfy constraints a
x
Y
Proof. Notice that the value of the product
can only be reduced by decreasing some a i . Thus it is
enough to bound the product from below with additional
constraint
The proof is by induction on m. The base case for
was shown in Proposition 4.1.
For the inductive step take
m. Thus we can use the inductive hypothesis to bound the
product by
the result follows.
Lemma 5.2. Let
2. Let
positive and satisfy
c

c
xr
e
Proof. We consider a function

xr
e
dened on domain k-dimensional
cube), and show that its maximum is at most 0, which will
complete the proof.
For this purpose let us extend the domain of f to
1. Observe that
D is an open and convex subset of R k , and that f has
continuous second partial derivatives in D. Also for every
point x 2 D, the Hessian matrix H(x) of f is diagonal,
and that the entries on the diagonal are strictly positive
es r+1 m(m 1)
r positive de-
nite, and so by Theorem 2.2 f is strictly convex. Since H is
a closed subset of D, Lemma 2.3 ensures that the values of
f on H are bounded from above by the values achieved at
the boundary of H.
After these preliminary observations let us prove the statement
of the lemma by induction on k. For the base case
assume that 1. There are two boundary cases. When
e
When
e
Thus f is bounded from above by 0.
For the inductive step we consider the values of f at the
boundary of H. Due to symmetricity of the function and
constraint conditions we can focus on two cases

xr
e
e

xr
e
and we can use the inductive hypothesis to bound f from
above. For the second case consider

xr
e
and we can use the inductive hypothesis again to bound
f from above.
Suppose that we have guessed the sizes of groups paged
in each round by a strategy that minimizes expected number
of cells paged until all mobile devices are found, and let
sd be these sizes (i.e., the strategy pages sr cells in
round c). In the next lemma we demonstrate
that when we use our heuristic with the same sizes
of groups paged in corresponding rounds then the expected
paging may be greater by at most factor e
Lemma 5.3. Let positive integers such that
Sd be any strategy for which
Td be the strategy in F that has
groups of the same cardinality jTr . Then the ratio of
expected number of cells paged until all mobile devices are
found is
EPS  e
Proof. When then the ratio EP T
1, which was
studied by other researchers [13, 18, 19]. Our proof focuses
on case when m  2.
Recall that by the construction the set
contains cells j that maximize the sum
us dene . For any r we divide the cells
in Ur [ Zr into three sets
. For each mobile device i we dene a i;r to
be the probability that the device i is in the cells Ar i.e.,
a
Similarly we dene b
By the theorem of the arithmetic and geometric means
[14] we have
(b m. Recall that for each mobile device
i we have consequently a i;r
By the choice of Zr we have that
a i;r
xr
If xr < m 1 then we can bound the product
Y
j2Zr
from below by 0, and the product
Y
j2Ur
from above by
then by Lemma 5.1 we can bound the
product
Y
j2Zr
from below by jTr+1 j (xr m+ 1), and the product
Y
j2Ur
from above by jSr+1 j xr
Recall that by Lemma 2.1
Without loss of generality let us assume that among
xd 1 only the rst k of them satisfy m 1  xr  m, and
the remaining satisfy 0  xr < m 1. Thus we can bound
the ratio from above by
c s2 x 1
It remains to show that the enumerator is bounded from
above by e
times the denominator. If then the
bound is trivial, so assume that k  1. But then by Lemma 5.2
the enumerator is never greater than e
times the denom-
inator. Thus the expected paging of the strategy
is at most e
times the expected paging of the strategy
This lemma immediately tells us that for any xed number
of rounds d we can nd an approximate paging strategy in
polynomial time because there are O(c d 1 ) strategies that
(because any selection of values for
some d 1 variables determines the value of the remaining
one variable). However this method is not satisfactory when
d and c grow, and so we seek a more scalable solution. We
achieve this by using dynamic programming.
5.2 Finding approximate solution using
dynamic programming
Now our goal is to nd a strategy in F that minimizes expected
paging among all strategies in F . For this purpose we
develop a dynamic programming algorithm that generalizes
an approach given by [13].
Take any 1  '  k  c and consider a class of strategies
of length ' that may page the last k cells and only these cells
during the ' rounds. Let be a strategy from this
class (so that
be a random variable equal to the number of cells paged by
this strategy given that at least one mobile device is located
among the last k cells (then P is at least 1). In the class we
can nd a strategy that minimizes the expected value of P
and denote this value by E('; k).
Observe that the value of E(d; c) is exactly the minimal
expected paging across all strategies in F . We need to show
that we can e-ciently nd a strategy that achieves E(d; c),
and as the rst step we prove a recursive formula for nding
the value of E('; k).
Lemma 5.4. The value of E('; k), 1  '  k  c, is equal
to:
when 1  k  c, and
min
Proof. We need to show that in each of the two equations
above the expression on the right side of the equal sign
is equal to the expression on the left side of the sign. The
rst equation is trivial because any strategy of length 1 that
pages exactly k cells during 1 round given that there is at
least one mobile device among these k cells has expected
number of cell paged equal to k.
In order to show the second equation we prove two in-
equalities. First we show that the expression on the right
side of the equal sign is never greater than E('; k). Let
be a strategy that may page the last k cells and
only these cells during ' rounds and that minimizes the expected
value of the number of cells P paged during the '
rounds given that at least one mobile device is located in
one of the last k cells. Observe that 1  jS1 j
because none of the groups can be empty. Let A be the
event that at least one mobile device is located among the
last k cells, and let B be the event that at least one mobile
device is located among the last k jS1 j cells. Observe that
array
07 for
26
28 gd

Figure

1: Algorithm for nding the sizes
of groups for a strategy that achieves e
matation factor.
the expected value of P is equal to
E(';
But
Y
Y
and so the expression on the right side of the second equation
is at most E('; k).
To show that the expression on the right side of the second
equation is never smaller than E('; observe that for
any x, 1  x  the value of the expression is
equal to the expected number of cells paged by a strategy
of length ' that may page the last k cells and only these
cells, x of which in the rst round, given that at least one
mobile device is among the last k cells. Hence the value of
the expression can never be smaller than the value E(';
that is the minimum of the expectation. This completes the
proof of the lemma.
During the calculation of E(d; c) we can nd the sizes of
groups for a strategy Gd that has expected paging
equal to E(d; c) (see Figure 1 for a pseudocode of an al-
gorithm. Lines 07 through 14 calculate the probabilities
that all devices are found by round r, for
Lines 15 through 25 evaluate the recursive formula given
in Lemma 5.4. Lines 26 through 29 nd the sizes of groups
for the approximation strategy that were calculated during
the evaluation of the recursive formula). This leads to the
main theorem of the paper.
Theorem 5.5. For any instance of the Conference Call
problem the strategy expected paging
and it can be found in O
space.
Proof. Take any instance of the Conference Call prob-
lem. By Lemma 5.3 the family F contains a strategy
that has expected paging at most e
times the minimal expected
paging of any strategy of length d. By Lemma 5.4
the dynamic programming nds a strategy
minimizes expected paging across all strategies in the fam-
ily. Thus the expected paging of the strategy
at most e
times the expected paging of any strategy of
length at most d.
We remark that the dynamic programming approach developed
in this section allows us to nd a strategy that minimizes
expected paging across a family of strategies that page
cells in any predened sequence.
5.3 Lower bound on performance
Finally we give a lower bound on the performance ratio of
our heuristic. Consider an instance of the Conference Call
problem with 2. Let
and the remaining probabilities are
set to 1
7 . By simple case analysis we can show that the
best strategy pages cells 2 through 6 in the rst round and
achieves 317expected paging, while the heuristic chooses to
page cells 1 through 5 in the rst round and achieves 320expected paging. This establishes a lower bound of 320
317 on
the performance ratio of our heuristic.
6. FUTURE WORK AND DISCUSSION
In this section we list some open problems and report some
of our results on our work in progress and then mention some
related work.
Our approximation solution has a small  1:58 approximation
factor and cannot be better than 320. Is there a
better approximation algorithm or even an approximation
scheme? So far we know an approximation scheme for a
subclass of the problem [7]. Here we assume that the set of
probabilities can be covered
by a constant number of real intervals of constant length.
This allows us to search the space of solutions exhaustively
in polynomial time.
In this paper we consider only oblivious strategies i.e.,
where the set of cells to be probed in each round is xed in
advance. It is interesting to also consider adaptive strategies
which determine, in each round, the set of cells to page
depending on the devices found in earlier rounds. Our NP-hardness
result applies to adaptive strategies as well since
for adaptive strategy is oblivious. One can easily
extend the heuristic presented in Section 5 to form an adaptive
strategy where, in each round, we calculate conditional
probabilities and based on their values we determine the
group of cells to page in the next round using the algorithm
presented in Figure 1. The analysis of the performance ratio
of the resulting algorithm stands as an open problem.
There are other interesting types of searches to consider.
A dual problem to the Conference Call problem is the Yellow
Pages problem in which we are searching for one out
of m possible devices. We showed [7] an m-approximation
algorithm based on a heuristic that is dierent from the one
considered in this paper. We also know that the heuristic
considered in this paper does not oer constant factor ap-
proximation. A problem that generalizes the two problems
is the Signature problem where we are looking for any k devices
out of the m devices. The conference call problem is
the case where and the yellow pages problem is the
case 1. Solutions to the signature problem can be
applied to the task of nding k managers out of m managers
to sign a document.
Another interesting direction is to extend the model. For
example due to bandwidth limitations in real systems it may
be reasonable to assume that at most a xed fraction of c
cells can be paged at any unit of time. Here we observe
that our approximation result generalizes to yield results in
this model: we can use Lemma 5.3 to show the existence
of an approximate strategy, and in Lemma 5.4 we can limit
the range for x accordingly to nd an appropriate strategy.
Another possible extension of the model is to assume that
when there is a device at a cell and we page the cell we do not
always nd out if the device is there (similar assumptions
have been considered [21]), and that the chances of nding
out decrease with the increase of the number of devices in
the cell. This models collision of response signals to the
paging signal emitted from the base station.
6.1 Related work
Burkard et al. [8] review a combinatorial optimization
problem related to the Conference Call problem. The problem
is called the Quadratic Assignment Problem [15] and
it is formulated as follows. Given two symmetric matrices
by c with non-negative entries
nd a permutation  that maximizes
i;j a i;j b (i);(j) .
It can be shown [7] that one can use a solution to the
Quadratic Assignment Problem to solve the Conference Call
problem for two mobile devices. If d is constant then the reduction
is polynomial time.
There are several results from Search Theory [21] that can
be used in location management. Search Theory deals with
nding a single object located among a set of cells as given by
a probability distribution. Searching consists of a sequence
of lookups of the cells. There is a cost associated with looking
up a cell. It is assumed that with some probability a lookup
may not nd an object in a cell even though the object is
located there. The goal is to decide which cells and when
to look up to maximize chances of nding the object under
constraints on the total cost of search. Awduche et al. [3]
consider a model where xed groups of cells are paged and
a probability is given that paging a cell does not detect a
device even though it is located at the cell. Authors show
how to apply results from Search Theory to minimize the
expected number of cells paged.
Another related search problem is the Combinatorial Group
Testing problem [9]. Using the terminology of our paper,
the model of CGT assumes that a paging of a subset of
cells (called items in CGT) returns whether a mobile device
(called defective in CGT) exists among the cells paged.
Thus the search may need to continue recursively by repag-
ing smaller and smaller sets in order to locate the single cell
where the mobile device exists (is located). In the model
that we study in this paper we assume that a paging of any
subset of cells returns all the devices that are located in one
of the cells that have been paged and for each of the devices
that have been found the cell where the device is located.
Hence no recursive repaging is needed.

Acknowledgements

. The work of the second author
would not be possible without generous support and encouragement
from his manager Michael Merritt while an intern
at AT&T Shannon Lab, whom he would like to thank.
The second author would also like to thank his advisor
Alex Shvartsman for very valuable discussions. The authors
would like to thank David Johnson, Je Lagarias, and S.
Muthukrishnan for discussion, and the anonymous PODC
reviewers for comments that improved the presentation of
the paper.
7.



--R

Location update optimization in personal communication systems.
Mobility Management in Next Generation Wireless Systems.
On Resource Discovery in Distributed Systems with Mobile Hosts.
Quantum Directories - a Search Engine for Mobile Users
Mobile Users: To Update or not to Update?
Tracking Mobile Users in Wireless Networks.
Establishing Wireless Conference Calls.
The Quadratic Assignment Problem.
Combinatorial Group Testing and Its Applications (2nd Edition).
EIA/TIA: Cellular radio-telecommunications intersystem operations
ETSI/TC: Mobile application part (MAP) speci
Computers and Intractability: A Guide to the Theory of NP-Completeness


Assignment problems and the location of economic activities.
Linear Algebra and Geometry.
Mobility Modeling
Adaptive Paging Algorithms for Cellular Systems.
Minimizing The Average Cost of Paging Under Delay Constraints.
Convexity and Optimization in Finite Dimensions.
Theory of Optimal Search.
--TR
Adaptive paging algorithms for cellular systems
On resource discovery in distributed systems with mobile hosts
Location update optimization in personal communication systems
Minimizing queuing delays and number of messages in mobile phone location
Mobile users
Minimizing the average cost of paging under delay constraints
Location management in cellular networks
Computers and Intractability

--CTR
Leah Epstein , Asaf Levin, The conference call search problem in wireless networks, Theoretical Computer Science, v.359 n.1, p.418-429, 14 August 2006
Amotz Bar-Noy , Yishay Mansour, Competitive on-line paging strategies for mobile users under delay constraints, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
approximation algorithms;NP-hardness;conference call;location management;convex optimization