Specific domain research

A: Mobile facility location

Mobile facility location problem is related to the location of mobile facilities serving a set of points moving continuously in the plane. Examples of such problems are the maintenance of the p-center and p-median for moving points under different metric. This problem has applications in mobile wireless communication networks when the broadcast range should contain all the customers getting service. Issues such as the motion parameters of the optimal location of the facilities, approximability results, etc. are all studied.

The results obtained so far are summarized below:

• 1-center
  It is easy to show that the velocity of rectilinear 1-center is bounded by $\sqrt{2}$ and the rectilinear 1-center can be maintained in an efficient KDS. Euclidean 1-center may move with arbitrarily high speed. When the facility is allowed to move with unit velocity, the center of mass of points is a good approximation of Euclidean 1-center which guarantees an approximation factor of $2-\frac{2}{n}$ and is shown to be asymptotically optimal. The center of the smallest bounding box of any set of points in the plane provides a $(1+\sqrt{2})/2$-approximat ion of the Euclidean 1-center, and this value is tight. In this case the speed of the facility is at most $\sqrt{2}$. Finally, we are able to show that for every $\epsilon > 0$, any $(1+\epsilon)$-approximate mobile Euclidean 1-center has velocity at least $1/(8\sqrt{\epsilon}))$ in worst case. The Steiner center provides a 1.1153-approximation of the Euclidean 1-center (the exact value is an irrational equation root) and has velocity at most $4/\pi$; both bounds are tight.
• 1-median
  Not only does the Euclidean 1-median have unbounded velocity in two dimensions, but there are sets of mobile points for which the motion of the Euclidean 1-median is discontinuous. The centre of mass provides a $(2-2/n)$-approximation of the Euclidean 1-median (still with unit velocity); this bound is tight. We introduce a new approximation to the Euclidean 1-median which we call the projection median. The projection median guarantees a $(4/\pi)$-approximation of the Euclidean 1-median but cannot guarantee any approximation factor less than $\sqrt{4/\pi2 + 1}$. The velocity of the projection median is at most $4/\pi$; this bound is tight.
• 2-center
  The Euclidean 2-center, rectilinear 2-center, and 2-means center (generalization of the center of mass) are all discontinuous in two or more dimensions. Using the rectilinear 1-center or the Steiner centre as a centre of reflection, we are able to define two approximations to the Euclidean 2-center that guarantee approximations of $2\sqrt{2}$ (tight) and $8/\pi$ (lower bound $2\sqrt{1+1/\pi2}$), respectively. The correponding bounds on velocity are $2\sqrt{2}+1$ and $8/\pi+1$. 
• 3-center and 2-median
  Even in one dimension, no bounded-velocity approximation of the Euclidean 3-center is possible. Similarly, no bounded-velocity approximation of the Euclidean 2-median is possible. Of course, these results apply to the rectilinear case as well since all $\ell_p$ norms are equal in one dimension. 

B: Instance-based learning

In the typical nonparametric approach to classification in instance-based learning (IBL) and data mining, random data (the training set of patterns) are collected and used to design a decision rule (classif ier). Instance based learning (IBL) algorithms attempt to classify a new unseen instance (test data) based on some ``proximal neighbour" rule, i.e. by taking a majority vote among the class labels of its proximal instances in the training or reference dataset. One of the most well known such rules is the k-nearest neighbor (k-NN) decision rule (also known as the lazy learning) in which an unknown pattern is classified into the majority class among the k-nearest neighbors in the train ing set. This rule gives low error rates when the training set is large. Geometric proximity graphs especially the Gabriel graph (a subgraph of the well known Delaunay triangulation) provides an elegant algorithmic alternative to k-NN based IBL algorithms. The main reason for this is that Gabriel graphs preserve the original nearest neighbour decision boundary between data points of different classes very well. This brings up up the problem of efficiently computing the Gabriel graph of large training data sets in high dimensional space. We have designed a new approach to the instance-based learning problem. The new approach combines five tools: first, editing the data using Wilson-Gabriel-editing to smooth the decision boundary, second, applying Gabriel-thinning to the edited set, third, filtering this output with the ICF algorithm of Brighton and Mellish, fourth, using the Gabriel-neighbor decision rule to classify new incoming queries, and fifth, using a new data structure that allows the efficient computation of approximate Gabriel graphs in high dimensional spaces.

C: Collection depots problem

We investigate the problem of locating a set of service facilities that need to service customers on a network. To provide service, a server has to visit both the demand node and one of several collection depots. A facility serving a customer dispatches a vehicle that visits the customer and returns to the facility through the collection depot which provides the shortest route. The goal is to minimize the travelled Euclidean weighted distance (minmax or minsum). This problem is a natural generalization of the classical facility location problem. We have analyzed the problem and showed that the collection depots problem in the plane using the Euclidean metric can be transformed to $O(p^2 n^2)$ number of different classical facility location problems and this bound is tight. Here p and n represent the number of depots and customers respectively. We also present 2-approximation algorithms for the problem, and show how some of the techniques developed can be applied to facility problems involving line barriers.