Mobile Facility Location
Overview
The traditional problems of facility location are set in a static setting;
client positions are fixed and a single location is selected for each facility.
Within the last few years, partly motivated by the applicability of mobile
computing to the wireless telecommunications industry, these
questions have been posed in the mobile setting. Given a set of clients,
each of which follows a continuous trajectory over time, the location of
a mobile facility is specified as a function of the client positions.
The suitability of a mobile facility is determined not only by the quality of
its optimization of the objective function but also by the maximum velocity and
continuity of its motion. These additional factors often require the optimal
location to be approximated, leading to new approximation strategies quite
different from previous static approximations.
This research presents a variety of challenges including identifying strategies
for defining motion for a set of facilities, deriving bounds on the continuity
and maximum velocity of the motion and on the quality of
approximation for a given strategy, deriving combinatorial bounds on
the complexity of the corresponding motion,
and developing efficient kinetic algorithms for maintaining the corresponding
positions for a set of mobile facilities as a function of client motion.
Specific mobile facility location problems considered include:
- the Euclidean 1-centre (centre of the smallest enclosing circle)
in the plane,
- Euclidean 2-centres in the plane,
- a Euclidean 1-median (Weber point) in the plane, and
- a 1-centre and 2-centres on trees.
Links
See this
Java applet
for a graphical implementation of some of these results.
Collaborators
David Kirkpatrick,
Christophe Paul
Publications
CGTA 2011,
DAM 2009,
CGTA 2009,
IJCGA 2008,
ISAAC 2007,
IJCGA 2006,
Ph.D. 2006,
FWCG 2005,
CCCG 2005,
CCCG 2004,
CCCG 2003
Load-Balanced Routing in Dense
Wireless Networks
Overview
A dense network can be modelled by a continuous region, where each node
corresponds to a point in the region.
Within this model, a routing policy assigns a continuous path to each
origin-destination pair.
A natural objective in selecting a routing policy is to minimize the
load passing through any single node.
While the average load is minimized by straight-line routing, such a routing
policy distributes the load non-uniformly, resulting in higher load near the
centre of the region.
The significance of this problem was highlighted in a recent paper by Karp and
Papadimitriou (MOBIHOC 2007).
We consider various one-turn rectilinear routing policies in rectangular
regions, resulting in a 33% reduction in the maximum load.
Our policies are simple to implement, being both local and memoryless.
We provide a lower bound that shows that no one-turn rectilinear routing policy
can reduce the maximum load by more than 39%.
Open questions include identifying policies that reduce the maximum load on
more general convex regions.
Collaborators
Lata Narayanan,
Evangelos Kranakis,
Danny Krizanc
Publications
JOIN 2009,
TAMC 2008
Rectilinear Crossing Number of
the Complete Graph
Overview
The rectilinear crossing number of the complete graph is a well-known
problem in geometric graph theory for which we improved on long-standing upper
and lower bounds.
The rectilinear crossing number of a graph G is the fewest number
of edge crossings attainable over all straight-edge drawings of G in the plane.
We describe new drawings of the
complete graph that had the fewest number of edge crossings known to date.
Since its publication, our work has generated considerable new activity in
the area, resulting in dozens of further improvements, some of which employ
our techniques to further improve bounds which, until our paper,
had remained unchanged for over thirty years.
Collaborators
Alex Brodsky,
Ellen Gethner
Publications
DM 2003,
EJC 2001