Wireless mesh networks based on the IEEE 802.11 technology have recently been proposed and studied as an approach to bridge the digital divide, and connect to distant rural areas. Point-to-point links are established in the nodes of such networks using high gain directional antennas. Some nodes are directly connected to the wired internet, and the others connect to these using a small number of hops.
Minimization of system cost is an important objective in these networks, since generally the rural populations are low-paying. The dominant cost in this setting is that of constructing the antenna towers which are needed for Line-of-Sight connectivity. The cost of a tower depends upon its height, which in turn depends upon the length of its links and the physical obstacles along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to achieve Line-of-Sight connectivity is minimized. We formulate this as a geometric coverage problem, show that it is NP-hard, and then present a constant factor approximation. For this we model it as an integer program and use a primal dual approach for the solution that is convenient to implement. We also present a polynomial time approximation scheme (PTAS) for the same problem without the constraints on available transmission power. This algorithm uses dynamic programming in conjunction with several Computational Geometry techniques.

A sensor is a small, battery-operated device that can be placed in some area to locally monitor its surroundings. A distributed sensor network is a collection of sensors which work together to monitor some universe. In this paper, we survey recent results pertaining to two different algorithmic questions motivated by applications in sensor networks. We consider the problem of positioning each of k sensors so as to cover a set of n points. We assume that each sensor has an adjustable radius and will cover all points who are within the radius of the sensor. We wish to cover all of the points with the k sensors so as to minimize the sum of the radii of each of the sensors. We model this problem as the algorithmic problem clustering to minimize the sum of radii. We will consider algorithms given by Gibson et al. Suppose now that the positions of the sensors are fixed, and each sensor has duration which represents the maximum amount of time that a sensor can be ``active''. The second problem we consider is scheduling a start time to each of the sensors so as to maximize the total amount of time that the entire area is covered. This problem is known as the sensor cover problem. We will consider the algorithm given by Gibson and Varadarajan for a special case of the sensor cover problem called Restricted Strip Covering.

A 0-1 matrix A is said to be in standard greedy form if for any two rows and two columns, the induced 2 by 2 submatrix does not have the form: a 0 in the bottom right corner, and 1 everywhere else. We consider the covering linear program for a positive vector c: min cx, subject to Ax \geq 1. We will describe an algorithm due to Hoffman, Kolen, and Sakarovitch [ SIAM J Alg. Disc. Meth., 1985 ] that establishes that an integral optimum to this linear program always exists, and that efficiently finds such an optimum. This result is employed by a recent algorithm due to Elbassioni, Matijevic, Mestre, and Severdija [ http://arxiv.org/abs/0809.0159 ] to obtain a constant factor approximation for guarding monotone polygonal chains in the weighted case.

In this paper, we give a O(log copt)-approximation algorithm for the point guard problem where copt is the optimal number of guards. Our algorithm runs in time polynomial in n, the number of walls of the art gallery and the spread \Delta, which is defined as the ratio between the longest and shortest pairwise distances. Our algorithm is pseudopolynomial in the sense that it is polynomial in the spread \Delta as opposed to polylogarithmic in the spread \Delta, which could be exponential in the number of bits required to represent the vertex positions. The special subdivision procedure in our algorithm finds a finite set of potential guard-locations such that the optimal solution to the art gallery problem where guards are restricted to this set is at most 3 copt. We use a set cover cum VC-dimension based algorithm to solve this restricted problem approximately.

In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.

I will present an elegant, randomized algorithm for obtaining an O(log^{2.5} n)-approximation to the minimum bandwidth problem on trees. This is due to Anupam Gupta (conf. version: SODA 2000, journal version: J. Alg. 2001).

We prove that for every centrally symmetric convex polygon Q, there exists a constant \alpha such that any (\alpha \cdot k)-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG?07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.

Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A,B,C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than $2\sqrt{2}\sqrt{2}$ vertices. We exhibit an algorithm which finds such a partition A,B,C in O(n) time.

Hierarchical graph decompositions play an important role in the design of approximation and online algorithms for graph problems. This is mainly due to the fact that the results concerning the approximation of metric spaces by tree metrics depend on hierarchical graph decompositions. In this line of work a probability distribution over tree graphs is constructed from a given input graph, in such a way that the tree distances closely resemble the distances in the original graph. This allows it, to solve many problems with a distance-based cost function on trees, and then transfer the tree solution to general undirected graphs with only a logarithmic loss in the performance guarantee. The results about oblivious routing in general undirected graphs are based on hierarchical decompositions of a different type in the sense that they are aiming to approximate the bottlenecks in the network (instead of the point-to-point distances). We call such decompositions cutbased decompositions. It has been shown that they also can be used to design approximation and online algorithms for a wide variety of different problems, but at the current state of the art the performance guarantee goes down by an O(log2 n log log n)-factor when making the transition from tree networks to general graphs. In this paper we show how to construct cut-based decompositions that only result in a logarithmic loss in performance, which is asymptotically optimal. Remarkably, one major ingredient of our proof is a distance-based decomposition scheme due to Fakcharoenphol, Rao and Talwar. This shows an interesting relationship between these seemingly different decomposition techniques. The main applications of the new decomposition are an optimal O(log n)-competitive algorithm for oblivious routing in general undirected graphs, and an O(log n)-approximation for Minimum Bisection, which improves the O(log1.5 n) approximation by Feige and Krauthgamer.