A polynomial-time approximation scheme for base station positioning in UMTS networks.
We consider the following optimization problem for UMTS networks: For a specified teletraffic demand and possible base station locations, choose positions for base stations such that  the construction costs are below a given limit, as much teletraffic as possible is supplied, the ongoing costs are minimal, and the intra-cell interference in the range of each base station is low.  We prove that for a particular specification of teletraffic (the so called demand node concept), this problem has a polynomial-time approximation scheme, but cannot have a fully polynomial-time approximation scheme unless
Introduction
1.1 CDMA Networks
During the planning stage for a new cellular network, one of the main tasks for a provider is
to decide where to place the base stations (i.e., the antennas). In order to accomplish this, data
about the expected teletrac demand is needed. A widely accepted way of describing phone trac
quantitatively is by providing so called demand node maps [Tut98]. A demand node represents
the center of an area with a certain teletrac demand. Each node stands for the same amount
of trac load; for the combinatorial properties of the problems we are going to discuss, it makes
no dierence if we simply think of one demand node as one user with a mobile phone. Thus,
densely populated areas will lead a large number of demand nodes while rural areas will lead to
a sparse distribution. Demand node maps are produced in a canonical way from given stochastic
data (a standardization for this is currently discussed by the International Telecommunication
Union [ITU99]).
When a base station is built, its signals reach all users within a certain range: We will say
that the corresponding demand nodes are supplied. For a base station i we will denote the set
of all supplied demand nodes by N i . For older network architectures, building one base station
could have an eect on other base stations. For example, neighbored base stations had to use
frequencies that are suciently far apart (frequency assignment problem). Also, interferences
between dierent base stations had to be considered; it could well be that a demand node is
located near to a base station i, nevertheless it is not supplied (i.e., not in N i ) because it is
disturbed by too strong signals from other stations.
Newer network architectures, as already existing in the United States (the IS-95 network) and
as currently developed in Europe (UMTS networks), rely on the so called code division multiple
access technology (CDMA), see [Rap96, Sect. 8.4.1 and Sect. 10.4]. This means that signals, both
from a base station and from a mobile station, are multiplied by a very large bandwidth signal
? Part of this work has been supported by NORTEL External Research.
called the spreading signal, a certain kind of pseudo-noise code sequence. All mobile users and all
base stations have their own pseudorandom codewords which are approximately orthogonal to all
other codewords. This implies that users in such a CDMA system use the same carrier frequency
and may transmit simultaneously. This leads to very high transfer rates. (In contrast to this, time
slots were reserved for each user in older time division multiple access networks.)
For the network planning stage, this implies the following: Dierent base stations can be considered
as independent from each other, because there are no frequency con
icts and no problems
with interference. On the other hand, the network has a soft capacity limit. Increasing the number
of mobile users supplied by a base station raises the noise
oor within the cell of the station.
While this will lead eventually even to technical limits (we might run out of dierent codewords),
it already much earlier causes a loss with respect to the quality of the transmitted signals.
The above considerations lead to some objectives that have to be aimed at by a provider
when planning a cellular network. We assume the provider has a demand node map of her area,
and furthermore, we assume that she identied possible locations for base stations (e.g., church
towers if the congregation agrees, roofs of industrial buildings if the company gets special phone
discounts, roofs of public buildings, etc. The provider now has to choose a subset of the possible
locations and built base stations there. The choice will be determined by the following:
1. To reach a high coverage of the area, as many of the given demand nodes as possible have
to be supplied. For each covered node, a certain gain will be obtained.
2. Usually, there is a certain maximal budget that the provider is allowed to spend during the
construction.
3. Built base stations have to be supported; hence they will cause ongoing costs.
4. Since we have no interference to take into account, it will cause no problem if a node
is covered by more than one station. (To the contrary, this is sometimes even a wanted eect,
because it allows a so called soft hando between stations as specied in the IS-95 standard
[Rap96, p. 407]; we do not take this into account here.) However, within the cell of each base
station, the background noise will raise if the number of supplied users raises. Higher noise will
lead to lower customer satisfaction and, hence, cause a certain loss.
Summing up all these gains and losses, a certain prot will be reached by the provider. The
goal is to maximize this prot.
1.2 Formal Denition of the Problem
Next, we present a formal denition of the problem described in Subsect. 1.1. Unless stated
otherwise we stipulate that all variables are considered as natural numbers.
Let B denote a set of possible base station locations, and let N denote a set of demand nodes.
In practical circumstances, the following requirements are certainly given:
(R1) The demand nodes and the possible base station locations are located in the Euclidean
plane.
(R2) Every base station has a maximal broadcast range r max (i). For every actually built
base station i we have to determine an actual broadcast range r(i)  r max (i). The sets N i
of those demand nodes that are supplied by i are then given by N
dist(i;
.
r
. In practice, D is some constant (currently, approximately
km). Additionally, in practice it is clear that every base station has a certain spatial
extension, and this implies that there is a constant d such that the distance between two
built base stations is at least d.
In the formal denition that follows, we consider even a slightly more general case: Instead of
requiring that D and d are constant, we only assume the following:
(R3') The maximal number of actually built base stations in any circular area with radius D is
bounded by some constant C.
It is clear that if D and d are constant, then we can determine our required constant C, but
not necessarily vice versa. Hence, if we assume (R1), (R2), and (R3'), this subsumes (R3), and
hence we certainly cover all practical cases.
The problem BSPC is now given as follows.
Base Station Positioning in CDMA Networks (BSPC):
Given are a set N of demand nodes and a set B of possible base station locations (both located
in the Euclidean plane), a budget b, a gain e for supplying a demand node, construction
costs c(i), ongoing costs o(i) for supporting a station at location i 2 B, a cost h(i;
the background noise that occurs when in the range of base station i a number of k demand
nodes is supplied, and a maximal broadcast range r max (i) for every base station i 2 B. Let
Bg. We require that the maximal number of actually built base
stations in any circular area with radius D is bounded by the constant C. The aim is to nd
a subset S  B of base stations to be built and a broadcast range r(i)  r max (i) for every
such that the overall construction costs
i2S c(i) are at most b and the following prot
P is maximal:
number of supplied demand nodes
z }| {
ongoing costs
z }| {
dist(i;
| {z }
cost of background noise
For the following complexity considerations, we dene the size of an instance as the length of
an encoding of all the above components, where numbers are encoded in binary.
1.3 Relation to Previous Work
Design problems for cellular networks have been examined with respect to frequency assignment
problems (see, e.g., [KvHK99]) and with respect to power range assignment (see [CPS00]).
However, the problem of positioning base stations in an optimal way has not been considered
in depth from a complexity-theoretic point of view. While simulation and planning tools (see
[TLT97]) and solutions based on linear programming (see, e.g., [MN99]) are known, not much has
been proven about (non-)solvability and (non-)approximability of arising combinatorial problems.
In [ESW98], optimum non-approximability results for planning problems for telecommunication
networks, where antennas are placed in balloons at a certain height, were given. In [BKK + 99],
an approximation algorithm for the problem of covering a plane area with cells while avoiding
buildings within dangerous range of a station was given. In [GRV00], three of the present authors
examined the design problem for cellular networks that use TDMA technology, e.g., GSM
networks.
However, turning to third generation cellular networks that use CDMA technology, the net-work
planning process is dierent from all the above. Compared to GSM networks, interferences
between dierent base stations no longer play an important role. On the other hand, for each
base station, the background noise within its cell has to be taken into account here. This posed
no problem for older networks. Mainly because of this point, the problem we consider here has
dierent combinatorial properties than the above mentioned problems. We present an approximation
algorithm based on the so called shifting strategy, which was introduced by Hochbaum and
Maass in [HM85]. In this technique, which is applicable to a lot of geometric problems, the plane
is divided in dierent ways, leading to dierent partitions. For each partition, an approximate
global optimum can be obtained by combining (exact) local optima. Then it is proved that for at
least one partition the obtained solution is near to the optimal solution. Our application of the
shifting strategy here is interesting, because even the solutions for particular partitions can only
be obtained in an approximate way, and we need an approximation algorithm for a knapsack-like
problem as a subroutine. Mainly because of this, the algorithm obtained here is more involved
than the one for GSM networks given in [GRV00].
1.4 Paper Organization
In the upcoming Sect. 2 we recall some basic notions. Sect. 3 contains the main technical part of the
paper. There we present an algorithm for BSPC, witnessing that this problem has a polynomial-time
approximation scheme. In Sect. 4 we prove that BSPC cannot have a fully polynomial-time
approximation scheme. Also, we examine a slightly restricted (but more practical) problem and
show that even this problem does not admit an FPTAS. Finally, Sect. 5 concludes.
Preliminaries
Let h(n)  1. We say that an algorithm A is an h(n)-approximation algorithm for a maximization
problem , if the solution produced by A for an input of size n is at least the optimal solution
divided by h(n). We say that an algorithm A is an h(n)-approximation algorithm for a minimization
problem , if the solution produced by A for an input of size n is at most the optimal
solution times h(n). In both cases, h(n) is called the approximation ratio [ACG
Informally, we will say that a problem is well-approximable if it can be approximated up to
any constant; formally: A problem  admits a polynomial-time approximation scheme (PTAS
for short) if, for every rational number r > 1, there is a polynomial-time algorithm A r that
r-approximates , see [ACG We will prove that BSPC admits a PTAS (Theorem 1).
For problems that have a PTAS, the question of course remains if there is a uniform approximation
scheme, working for all ratios r with a runtime which is polynomial in the input length and
1=(r 1). This would mean that the problem has a so called fully polynomial-time approximation
scheme
An optimization problem  is NP-hard, if every language L 2 NP reduces to  via polynomial-time
Turing-reductions, see [ACG be a polynomial; then  p denotes the problem
obtained by restricting  to only those instances I for which all numbers, that occur as components
of input I, are bounded by p(jIj). An optimization problem  is strongly NP-hard if there
is a polynomial p such that the problem  p is already NP-hard [ACG
3 An Approximation Scheme for BSPC
Let the given set N of demand nodes in the plane be enclosed in the rectangular area A. We x an
integer l > 0, the so called shifting parameter. This number will later determine the approximation
ratio of our algorithm.
Our algorithm consists of three steps.
Step 1. Fix a division of A into horizontal and vertical strips of width D, where each strip
is left (up) closed and right (down) open. By considering groups of l consecutive horizontal and
vertical strips of width D, we obtain a partition of A into several squares of size (lD) 2 , which form
a grid of width lD; see Fig. 1. Notice that the number of such squares is possibly superpolynomial
in the input size, but in this case almost all squares do not contain any demand node. Therefore,
it suces to consider the small number (bounded by jN j) of non-empty squares, i.e., squares
containing at least one demand node. A list s of these non-empty squares can be eciently
computed, since for each demand node we can determine the square containing this demand node.
In each such square s i we delete all base station locations that are in the border-strips of width
D; thus we obtain a new square t i of the same size but with no base station locations in distance
less than D to the border; see Fig. 2.
Step 2. For each square t i and each number m  b
lD
lD
lD lD
Fig. 1. A partition of the plane.
Dots represent base stations.
(we call this m a local budget) we dene a set S(i; m) of
base stations located in t i such that (i) the cost of this set
is  m, i.e.,
we build the
base stations in S(i; m) we obtain the maximal prot in t i
possible with a local budget  m (we refer to this maximal
prot as P (i; m)). Note that we cannot compute all the sets
m) and prots P (i; m) for 1  i  n and m  b, since
there are exponentially many. However, a single P (i; m)
can be computed by exhaustive search, since in each t i we
can build at most base stations; this follows by
the simple fact that we can not build more than C base
stations in any circular area with radius D, and t i can be
covered by l 2 such disks of radius D. Since the prot of
building no base station is 0, the values of P (i; m) are all
at least 0. Moreover, it is easy to see that, for each xed i, P (i; m) as a function in m is monotonic
increasing. Now we have to combine these local solutions in a nearly optimal way, which turns out
as a kind of knapsack-problem. We have to distribute the overall budget b to the single squares,
i.e., for each t i we have to nd a local budget m such that the sum of all these local budgets is at
most b and the sum of all local prots, P (i; m), is (almost) maximal.
We show that this knapsack-like problem admits a full polynomial time approximation scheme
for short). This means that on input of some r and a problem instance I, we can compute
in polynomial time in jIj + r an approximated solution with relative error  1=r. The proof is
based on an idea of [IK75] (see also [Pap94, pp. 305]), showing that the knapsack problem admits
an FPTAS.
In the following we describe the way this approximation algorithm works. Let p
n. Note that P max is an upper bound for the
obtainable prot. In the following we only consider prots that are multiples of 2 k where
blog(p max =rn)c. We will see that this is sucient to obtain a good approximative solution. Now
determine all b
(using
binary search this is possible in time polynomial in (n  p max =2 k )  log b. This is polynomial in
log b, since p max =2 k  2rn and P (i; ) is a monotone increasing function). The values b i;p
give us complete information about the function P (; ) disregarding the last k bits of the prot.
Let W (j;
lD
lD
lD lD
Fig. 2. Clearing border strips by
deleting all base stations outside the
shaded squares.
for Hence the function
W (j; p) gives us the minimal construction costs we have to
invest into the rst j squares such that the obtained prot
is at least p  2 k (disregarding in each square the last k bits
of the prot). Since P max =2 k  2rn 2 we can determine all
values W (j; p) in time polynomial in n+ r using a dynamic
programming technique. More precisely let W (1;
for
. Choose the
largest
p such that W (n;
p)  b. This means that we can
reach a prot
we distribute an overall investment
of W (n;
p) in a suitable way to the squares.
By we denote the local budgets that are spent
in squares in order to obtain this prot
we estimate the relative error of this solution. For this we x an optimal solution
that the sum of all
Assume the contrary, and let ^
. So the sum of the local
budgets b i;^p i
is  b and the sum of the ^
i is by assumption greater than
p. This is a contradiction
to the choice of
since
was chosen to be the maximal approximate solution. This proves the
claim.
2:
The rst inequality holds since the represent an optimal solution, the second inequality
follows from the denition of  b , the third because of Claim 1, and the fourth follows by
simple arithmetic. This proves Claim 2.
Hence, the approximate solution 2 k
p is at least the optimal solution minus 2 k n. Since the value
p max is a lower bound for the overall optimal solution, we conclude that the approximate solution
has a relative error of at most n  2 k =p max . Since p max =2 k  rn, this error is bounded from the
above by 1=r.
Step 3. Clearly there are l 2 dierent ways of partitioning A by a grid of width D into one
of width lD, because each xed partition can be shifted down (to the right) by D, 2D,
(l 1)D before we obtain the same partition again; see Fig. 3.
Denote the resulting shift partitions by P Notice that such a partitioning can be
described by the coordinates of a single point in the plane. Therefore, we can x a partitioning
of A in polynomial time even if the area A is large. If we choose l, we obtain for every
partition P i an approximate solution p i for the knapsack problem which has a relative error  1=l.
Under all these solutions we choose one with maximal prot.
This concludes the description of the algorithm. Next
lD
lD
lD
lD
Fig. 3. A second partition (dashed
lines), obtained by moving the rst
one right by 2D and down by 3D.
we want to show that the relative error of the whole algorithm
is at most 5=l. We x an optimal solution of the given
problem instance I. Let the prot of this solution be
p and
the set of built base stations be S. Now for every base station
be the set of demand nodes supplied by i.
We assume w.l.o.g. that the sets N i are pairwise disjoint. (If
some demand node occurs in more that one of these sets, we
simply delete it arbitrarily from some of the N i in order to
achieve disjointness.) Now we assign to each i 2 S the value
dist(i;
.
If a set R of base stations is not built, then the prot lost
is at most
This holds because
{ the number of demand nodes that are no longer supplied when we do not build base stations
in R is at most
{ the ongoing costs for supporting i is exactly o(i), and
{ the cost of background noise we prevent by not building i is exactly
dist(i;
Note that each x i is non-negative, since otherwise the base stations with negative x i could be
omitted and thus a solution with higher prot could be achieved.
For each partition P j , let R j be the set of base stations built in the optimal solution that are
located in a border strip of that partition. We consider the sums C
where C j is an upper bound for the prot we loose in partition j by deleting all base stations in
the border strips.
Since for each base station i 2 S there exist exactly 4l 4 partitions where i is on a border
strip, each x i occurs in exactly 4l 4 of these C j . Hence the sum of all C j is equal to
(4l
since it holds that
p. However, since there are l 2 partitions
in total, it follows, using a pigeon hole argument that there must be one partition j 0 with
l
p. By building only the base stations of the optimal solution which are not in R j 0
we will achieve a prot of at least l 4
p. If we consider the new problem instance I j 0 in which all
base station locations in R j 0
are deleted, then the solution of the knapsack problem for partition
is the optimal solution for I j 0 . We have already seen that we can solve this knapsack problem
with a relative error  1=l. So using the partitioning
we nd a solution which has an overall
prot
l
l
ll
l
.
Hence the prot computed by our algorithm for partition P j 0
is an approximation of ^
with
relative error  5=l. Since we have chosen the largest prot over all partitions, we obtain at least
the value (1 5=l)^p.
Since l can be chosen beforehand, we see that for every approximation ratio  > 1 (respectively,
for every relative error > 0) we obtain a corresponding polynomial time algorithm A  for the BSPC
problem. Hence we have proven the following theorem.
Theorem 1. The problem BSPC admits a PTAS.
Hardness Results
The geometric disk cover problem (DC) is dened as follows: Given is a set N of points in the
plane, a radius r > 0, and a budget b 2 N. The question is if there is a set B of points in the
plane, jBj  b, such that every element from N is covered by a disk with radius r centered in one
of the points in B. (If a point j lies in distance exactly d from some i 2 B, i.e., on a circle with
radius r around i, we stipulate that it is covered by a disk centered in i.) It is known that DC is
NP-complete [FPT81], even in the strong sense [HM85].
Lemma 2. For C  12, the problem BSPC is strongly NP-hard.
Proof. First, we show that BSPC is NP-hard by constructing a Turing-reduction from DC.
Given is the set N of points in the plane, the radius r, and the budget b. We x an arbitrary
triangulation T which consists of equilateral triangles with side length
3  r. (Note that this can
be xed by two points of the plane). It is easy to see that the vertices of T (interpreted as centers
of disks) allow a covering of the plane by disks of radius r. Moreover, it can be shown that each
circular area with radius r (respectively, 2r) can be covered by 5 (respectively, 12) disks with
centers in T and radius r. For a given circular area with center i and radius r (respectively, 2r),
a minimal covering set T (i)  T can be determined in polynomial time.
We set to be the set of all points i in the plane such that if we draw a
circle with center i and radius D, then at least two elements from N are located on this circle.
be the union of B 0 and all T (i) for
r
Let us consider an optimal solution of this instance. We want to see that in any circular area
with radius D there are no more than stations. Otherwise there would exist
a circular area with center i and radius r that contains more than 12 base stations. Of course
the area that is covered by these base stations is contained in the circular area with center i and
radius 2r. So we would obtain a better solution if we replace these base stations by T (i). This
is a contradiction to our assumption and it follows that in the optimal solution in any circular
area with radius D there are no more than base stations. This shows that for our
reduction the values C  12 cause no restriction to BSPC.
Now it is clear that in order to obtain maximal prot, we have to supply as many nodes in
N as possible with the given budget. Hence all nodes in N can be covered using at most b disks
of radius r i all nodes in N can be supplied by building b base stations with range D i the
maximal prot is jN j.
Besides those numbers already present in the given DC instance, the only non-constant numbers
occurring in a constructed BSPC instance are the coordinates of the points in B, which can
be written down with a number of bits proportional to those needed for coordinates in the input
set N , and the value b, which is certainly at most jBj, hence bounded by a polynomial in the
input length. Therefore, there is a polynomial p such that BSPC p is NP-hard, and thus, BSPC is
strongly NP-hard. ut
Theorem 3. For C  12, the problem BSPC does not admit an FPTAS.
Proof. The value of an optimal solution of an instance of BSPC p , for p as in the proof of Lemma 2,
is at most jN j, hence polynomial in the input length. Thus, this problem does not have an FPTAS
by [ACG
Hardness of a Restricted Problem
Let us come back to requirement (R3) in Subsect. 1.2. The denition of the problem BSPC uses
(R3'), which is slightly weaker than what is required in (R3). Therefore, the question remains if
the practically relevant BSPC problem, i.e., restricted to requirement (R3) with constant values
for d; D, admits even an FPTAS. In the reduction from disk cover, given in the proof of Lemma 2,
we were easily able to conclude that a constant C, as required in the denition of the general
BSPC problem, exists. However, the reduction does not guarantee that D and d are constant.
Hence, the above reduction does not show that the restricted BSPC problem is hard.
Nevertheless, it can be shown, using a modication of the reduction from 3SAT to DC given
in [FPT81], that the restricted BSPC problem is strongly NP-hard; hence we conclude:
Theorem 4. The problem BSPC, restricted to the case that d and D are constant and D  d,
does not admit an FPTAS, unless
Proof. (Sketch.)
Fix d; D, where D  d. Given a 3-CNF formula , we rst construct an instance of DC with
loops for all variables in  as in [FPT81, Theorem 4, pp. 134f]. Let N be the set of nodes on
these loops. The proof given in that paper shows that all nodes in N can be covered by b disks of
suitable xed radius d i  is satisable, where b is the value N min determined in the proof from
[FPT81]. Moreover, a set B of possible disk centers can be determined, given , such that, if
is satisable, then all nodes can be covered using b disks centered at some of the points in B. A
careful analysis shows that any two points in B are at distance at least d.
Now, the reduction from 3SAT to restricted BSPC maps a given formula  to the BSPC
instance, given by N;B; b as above, and
N. As in Lemma 2, in order to obtain maximal prot, we have to supply as many nodes
in N as possible with the given budget. Hence  is satisable i all nodes in N can be supplied
by building b base stations with range r i the maximal prot is jN j.
This proves that the restricted version of BSPC is NP-complete. That the problem is actually
strongly NP-complete follows from the following facts: Coordinates for points in B and N can be
described (as in [FPT81]) using small integers, the value of b is at most jN j, and all other numbers
r, c, e, o, and h are constant.
That restricted BSPC does not have an FPTAS follows, since even the subset of BSPC, used
in the above reduction, is strongly NP-hard, and that the maximal prot is bounded by jN j. ut
5 Conclusion
We examined the complexity of nding an optimal way to built base stations in order to supply
a specied demand of teletrac in a CDMA network. The meaning of \optimal" here took a
number of eects in account, such as gain from supplied users, construction costs and ongoing
costs for base stations, and higher customer satisfaction if the background noise is low. We proved
that an Euclidean version of the problem, which is still good enough for practical purposes, has
a polynomial-time approximation scheme but no fully polynomial-time approximation scheme.
The sets N i of demand nodes supplied by a base station i were for our above algorithm just the
sets of demand nodes that are located within a certain distance from station i. One might argue
that this is unrealistic; e.g., it might be that a demand node is located near to a base station,
but nevertheless it is not supplied because there is a high building in between. However, for our
approximation scheme given in Sect. 3, it is only important that we nd some number D such
that every N i is located within a circle of radius D around base station i. The N i itself can be
of arbitrary shape, for example taking skyscrapers or other particularities of the landscape into
account. Hence we do not rely on an Euclidean metric for station signals. Our algorithm is still
polynomial time, if for a given station i and a demand node j it can be determined in polynomial
time, if j is supplied by i.
If we look at an incremental version of the base station positioning problem, where as an
additional input we get a network of already existing base stations that we have to extend by
building base stations up to a given budget, it can be observed that a modication of our algorithm
shows that this problem also has a PTAS. The only point that changes in the algorithm in Sect. 3
is the computation of the local prots P (i; m). An interesting topic for further research could be
to examine a \build on demand" problem, where new teletrac requests arise online, and we have
to update our network continuously.

Acknowledgement

. We are very grateful to Phuoc Tran-Gia and Kenji Leibnitz for giving us a
tutorial about CDMA technology. During the discussions in these meetings, the formal denition
of the BSPC problem evolved. We also acknowledge helpful discussions with Klaus W. Wagner.



--R

Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability
Station layouts in the presence of location constraints.
A compendium of NP optimization problems.
The power range assignment problem in radio networks on the plane.
Positioning guards at
Optimal packing and covering in the plane are NP-complete
Computers and Intractability

Approximation schemes for covering and packing problems in image processing and VLSI.
Fast approximation algorithms for the knapsack and sum of subset problems.

Optimal solutions for a frequency assignment problem via tree-decomposition
Optimum positioning of base stations for cellular radio networks.
Computational Complexity.
Communications - Principles and Practice


--TR
Approximation schemes for covering and packing problems in image processing and VLSI
Analysis of a local search heuristic for facility location problems
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Communications
Complexity and Approximation
Station Layouts in the Presence of Location Constraints
The Power Range Assignment Problem in Radio Networks on the Plane
Optimal Solutions for Frequency Assignment Problems via Tree Decomposition
Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result

--CTR
Christian Glaer , Steffen Reith , Heribert Vollmer, The complexity of base station positioning in cellular networks, Discrete Applied Mathematics, v.148 n.1, p.1-12,
Larry Raisanen , Roger M. Whitaker , Steve Hurley, A comparison of randomized and evolutionary approaches for optimizing base station site selection, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Roger M. Whitaker , Larry Raisanen , Steve Hurley, The infrastructure efficiency of cellular wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.6, p.941-959, 19 August 2005
Kevin P. Scheibe , Laurence W. Carstensen, Jr. , Terry R. Rakes , Loren Paul Rees, Going the last mile: a spatial decision support system for wireless broadband communications, Decision Support Systems, v.42 n.2, p.557-570, November 2006
Roger M. Whitaker , Steve Hurley, On the optimality of facility location for wireless transmission infrastructure, Computers and Industrial Engineering, v.46 n.1, p.171-191, March 2004
Larry Raisanen , Roger M. Whitaker, Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem, Mobile Networks and Applications, v.10 n.1-2, p.79-88, February 2005
Hierarchical parallel approach for GSM mobile network design, Journal of Parallel and Distributed Computing, v.66 n.2, p.274-290, February 2006
Filipe F. Mazzini , Geraldo R. Mateus , James Macgregor Smith, Lagrangean based methods for solving large-scale cellular network design problems, Wireless Networks, v.9 n.6, p.659-672, November
Michael R. Fellows, Parameterized complexity: the main ideas and connections to practical computing, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
approximation algorithms;network design